|
|
|
|
|
## [$AcWing$ $1072$ 树的最长路径](https://www.acwing.com/problem/content/description/1074/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
给定一棵树，树中包含 $n$ 个结点（编号$1$~$n$）和 $n−1$ 条无向边，每条边都有一个权值。
|
|
|
|
|
|
现在请你找到树中的一条最长路径。
|
|
|
|
|
|
换句话说，要找到一条路径，使得使得路径两端的点的距离最远。
|
|
|
|
|
|
注意：路径中可以只包含一个点。
|
|
|
|
|
|
**输入格式**
|
|
|
第一行包含整数 $n$。
|
|
|
|
|
|
接下来 $n−1$ 行，每行包含三个整数 $a_i,b_i,c_i$，表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。
|
|
|
|
|
|
**输出格式**
|
|
|
输出一个整数，表示树的最长路径的长度。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤n≤10000,$
|
|
|
$1≤a_i,b_i≤n,$
|
|
|
$−10^5≤c_i≤10^5$
|
|
|
|
|
|
**输入样例：**
|
|
|
```cpp {.line-numbers}
|
|
|
6
|
|
|
5 1 6
|
|
|
1 4 5
|
|
|
6 3 9
|
|
|
2 6 8
|
|
|
6 1 7
|
|
|
```
|
|
|
|
|
|
**输出样例：**
|
|
|
```cpp {.line-numbers}
|
|
|
22
|
|
|
```
|
|
|
|
|
|
### 二、朴素版本$dfs$【不能$AC$】
|
|
|
朴素$dfs$: 对每个点求最远点最大距离, 所有结果的$max$就是结果.
|
|
|
通过 $11/17$. 然后$TLE$, 效果不是很理想。
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 10010, M = N << 1;
|
|
|
// 暴力搜索，从每个节点为根出发，遍历整根树，找出距离自己的最大距离,然后每个最大距离取min
|
|
|
// 11/17,其它TLE,无法AC
|
|
|
int n;
|
|
|
int ans; // 树的直径
|
|
|
// 邻接表
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
void dfs(int u, int fa, int sum) {
|
|
|
if (sum > ans) ans = sum;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue; // 不走回头路
|
|
|
dfs(v, u, sum + w[i]);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
// 初始化邻接表
|
|
|
memset(h, -1, sizeof h);
|
|
|
|
|
|
cin >> n;
|
|
|
for (int i = 1; i < n; i++) { // n-1条边
|
|
|
int a, b, c;
|
|
|
cin >> a >> b >> c;
|
|
|
add(a, b, c), add(b, a, c); // 无向图
|
|
|
}
|
|
|
|
|
|
// 多次dfs,是TLE的罪魁祸首
|
|
|
for (int i = 1; i <= n; i++) dfs(i, 0, 0);
|
|
|
|
|
|
// 输出结果
|
|
|
printf("%d", ans);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 三、两次$dfs$解法 【不能$AC$】
|
|
|
|
|
|
#### 优点：思路简单
|
|
|
|
|
|
#### 缺点：只适用于不带负边的树
|
|
|
此题目中的第$15$组数据，可以$HACK$掉这种作法(此组数据中带有负权边)
|
|
|
|
|
|
**算法**：从任意点$a$出发, 找到距离$a$最远的点$t1$, 然后从$t1$出发, 找到距离$t1$最远的点$t2$,$t1$和$t2$的距离即为我们要找到结果.
|
|
|
|
|
|
<font color='red' size=4><b>黄海注：在$AcWing$ $1073$中，没有出现边权是负值的情况，所以两遍$dfs$大法好用 : [传送门](https://www.cnblogs.com/littlehb/p/15786805.html)</b></font>
|
|
|
|
|
|
这里我就不赘述证明了，想看证明的同学可以移步洛谷里面一个题的题解，里面有证明: **[传送门](https://www.luogu.com.cn/problem/solution/P5536)**,或者看一下$yxc$本题的视频教程。
|
|
|
|
|
|
|
|
|
|
|
|
通过了 $15/17$个数据,剩余两个测试点，居然是$WA$,真是，唉~
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 10010, M = N << 1;
|
|
|
|
|
|
int ans; // 保存最长路径
|
|
|
int t; // 保存找到的最远点
|
|
|
int n;
|
|
|
|
|
|
// 邻接表
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
void dfs(int u, int fa, int sum) {
|
|
|
if (sum > ans) {
|
|
|
ans = sum; // 记录最大距离
|
|
|
t = u; // 记录最远的点t1
|
|
|
}
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue;
|
|
|
dfs(v, u, sum + w[i]);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(h, -1, sizeof h);
|
|
|
cin >> n;
|
|
|
for (int i = 1; i < n; i++) {
|
|
|
int a, b, c;
|
|
|
cin >> a >> b >> c;
|
|
|
add(a, b, c), add(b, a, c);
|
|
|
}
|
|
|
dfs(1, 0, 0); // 先找到点距离点1最远的点t1
|
|
|
|
|
|
dfs(t, 0, 0); // 找到距离点t1->t2最远的点t1
|
|
|
|
|
|
printf("%d", ans);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 四、最长+次长解法【终极解法】
|
|
|
|
|
|
**树的最长路径** ，也称为树的 **直径** ,直径 **不唯一**
|
|
|
|
|
|
我们知道：树上 **任意两点** 的路径是 **唯一** 确定的，因此我们可以暴力枚举 **起点** 和 **终点** 找出最长路径
|
|
|
|
|
|
如果这样做的话，我们来思考一下时间复杂度：
|
|
|
|
|
|
> 枚举 **起点** 和 **终点** — $O(n^2)$
|
|
|
> 找出两点之间的路径长度 — $O(logn)$
|
|
|
|
|
|
但是光是枚举 **起点** 和 **终点**，**时间复杂度** 就直接拉满了，显然这种做法不可取。
|
|
|
|
|
|
既然这 $O(n^2)$ 条路径不能 一一枚举，那么有什么方式可以把他们 **分类枚举** 呢？
|
|
|
|
|
|
考虑换一种 **枚举方式**：枚举路径的 **起点和终点** $→$ 枚举路径的 **中间节点**
|
|
|
|
|
|
<font color='red' size=4><b>注：枚举中间节点非常妙，因为树节点只有$n$个，全遍历一遍也没啥问题，怕就怕双重循环的两两一组。如此，就成功的将双重循环$O(N^2)$时间复杂度降为$O(N)$的时间复杂度。方法就是在遍历过程中，努力构建关于当前节点$u$的多重信息，然后用这些信息去组装出直径最大值,果然有$dp$的味道在里面~</b></font>
|
|
|
|
|
|
我们先讨论一下，对于给定拓扑结构的树里的任意节点，经过它的路径有哪些：
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2021/08/25/55909_2a282a8605-IMG_61398D0A7BFC-1.jpeg'></center>
|
|
|
|
|
|
观察 **红色节点【本质上就是对于树中的任意节点均同此理】**，经过它的路径有：
|
|
|
|
|
|
* 以其 **子树中的某个节点** 作为 **起点**，以它作为 **终点** 的 **粉色路径**
|
|
|
* 以其 **子树中的某个节点** 作为 **起点**，以 **子树中的某个节点** 作为 **终点** 的 **蓝色路径**
|
|
|
* 以其 **子树中的某个节点** 作为 **起点**，以 **非其子树的节点** 作为 **终点** 的 **橙色路径**
|
|
|
|
|
|
对于第 $1$ 种情况，可以 **直接递归处理其子树，找出到当前子树根节点最长的路径长度即可**
|
|
|
对于第 $2$ 种情况，在处理第 $1$ 种情况时，顺便找出 $1$ 类路径的 **次长路径**，再把 **最长** 和 **次长** 拼在一起，就是第 $2$ 种情况
|
|
|
对于第 $3$ 种情况，可以把它归类为其 **祖先节点** 的第 $1,2$ 种情况，让其 **祖先节点** 去处理即可
|
|
|
|
|
|
**实现代码**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 10010, M = N << 1;
|
|
|
int n; // n个结点
|
|
|
|
|
|
// 链式前向星
|
|
|
int h[N], e[M], w[M], ne[M], idx;
|
|
|
void add(int a, int b, int c) {
|
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
int ans; // 答案,直径
|
|
|
int mx1[N], mx2[N]; // mx1[i],mx2[i]:经过i点的最长,次长长度是多少
|
|
|
|
|
|
void dfs(int u, int fa) {
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (v == fa) continue; // v点访问过了
|
|
|
|
|
|
// 走v子树,完成后，v子树中每个节点的mx1[v],mx2[v]都已经准备好，u节点可以直接利用
|
|
|
dfs(v, u);
|
|
|
|
|
|
// w[i]:u->v的路径长度,mx1[u]:最长路径,mx2[u]:次长路径
|
|
|
int x = mx1[v] + w[i];
|
|
|
if (mx1[u] <= x) // v可以用来更新u的最大值
|
|
|
mx2[u] = mx1[u], mx1[u] = x; // 最长路转移
|
|
|
else if (mx2[u] < x)
|
|
|
mx2[u] = x; // 次长路转移
|
|
|
}
|
|
|
// 更新结果
|
|
|
ans = max(ans, mx1[u] + mx2[u]);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
memset(h, -1, sizeof h); // 初始化邻接表
|
|
|
for (int i = 1; i < n; i++) { // n-1条边
|
|
|
int a, b, c;
|
|
|
cin >> a >> b >> c;
|
|
|
add(a, b, c), add(b, a, c); // 换根dp一般用于无向图
|
|
|
}
|
|
|
dfs(1, 0); // 任选一个点作为根节点,此处选择的是肯定存在的1号结点
|
|
|
cout << ans << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
