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$ # 解题思路 本题考虑用动态规划的思路去解题 考虑到建图时需要建立联通的无向图， 且图的每一个顶点都可能是树根， 因此不妨设置1为树根 为了求得树的最长路径， 可以定义如下的状态表示： - 设`dist[i]`为以顶点$i$为根的子树上， 通过顶点$i$的所有路径的最大值， 则`max(dist[i])`即为答案 - 为了求得以$i$为根的子树的最大值， 需要知道从顶点$i$向下遍历时， 所走过的最远的距离`d1[i]`和次远的距离`d2[i]` - 因此这里需要采用$dfs$的策略， 递归的更新`d1`和`d2`， 来达到解题的目的 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 2e5 + 10; int n; int h[N], e[N], ne[N], w[N], idx; int ans; void add(int a, int b, int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++; } int dfs(int x, int father) { int dist = 0; int d1 = 0, d2 = 0; for(int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if(j == father) continue; int t = dfs(j, x) + w[i]; if(t >= d1) d2 = d1, d1 = t; else if(t >= d2) d2 = t; dist = max(dist, t); } ans = max(ans, d1 + d2); return dist; } 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(1, -1); cout << ans << endl; return 0; } ``` 最后修改：2025 年 02 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏