Loading... # 题目描述 给定一棵树，树中包含$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$ # 解题思路 这道题与[ACWing 1072 树的最长路径](http://y0k1n0.online/index.php/archives/43/)类似， 不同点在与这道题求的是顶点$i$到其他点的最大值最小对应的特定的顶点 在上一道题中， 我们求得了经过以当前顶点为树根的子树向下便利的最大值和次大值， 但是为了求顶点$i$到其他所有点的最大值， 还有一种可能是顶点$i$的父节点$j$到其他节点的最大值加上边`edge[i][j]`的值才是最终答案， 因此需要进行两次dfs遍历 - 第一次遍历：求出所有顶点向下遍历的最大值和次大值， 同时记录最大值是由哪个顶点转移得到的 - 第二次遍历：求出所有顶点向上遍历的最大值 - 如果节点$i$的父节点$j$向下遍历的最大值经过节点$i$， 则节点$i$向上遍历的最大值是由节点$j$向下遍历的次大值得到的 - 反之， 则是由节点$j$向下便利的最大值得到的 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 2e5 + 10; const int INF = 0x3f3f3f3f; int n; int h[N], e[N], ne[N], w[N], idx; int d1[N], d2[N], pass[N], up[N]; void add(int a, int b, int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++; } int dfs_d(int x, int father) { d1[x] = d2[x] = - INF; for(int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if(j == father) continue; int t = dfs_d(j, x) + w[i]; if(t >= d1[x]) { d2[x] = d1[x], d1[x] = t; pass[x] = j; } else if(t > d2[x]) { d2[x] = t; } } if(d1[x] == -INF) d1[x] = d2[x] = 0; return d1[x]; } void dfs_u(int x, int father) { for(int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if(j == father) continue; if(pass[x] == j) { up[j] = max(up[x], d2[x]) + w[i]; } else { up[j] = max(up[x], d1[x]) + w[i]; } dfs_u(j, x); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 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_d(1, -1); dfs_u(1, -1); int ans = INF; for(int i = 1; i <= n; i ++) { int t = max(d1[i], up[i]); ans = min(ans, t); } cout << ans << endl; return 0; } ``` 最后修改：2025 年 02 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏