【题目来源】https://www.acwing.com/problem/content/1074/https://www.luogu.com.cn/problem/B4016【题目描述】给定一棵 n 个结点的树树没有边权。请求出树的直径是多少即树上最长的不重复经过一个点的路径长度是多少。【输入格式】第一行输入一个正整数 n表示结点个数。第二行开始往下一共 n−1 行每一行两个正整数 (u,v)表示一条边。【输出格式】输出一行表示树的直径是多少。【输入样例】51 22 44 52 3​​​​​​​【输出样例】3【数据范围】数据保证1≤n≤10^5。【算法分析】● 什么是树的直径树上任意两结点之间最长的简单路径即为树的直径。若无负权边可以采用两次 DFS 或者树形 DP的方法在 O(n) 时间求出树的直径若有负权边则只能采用树形 DP求解树的直径。显然一棵树可以有多条直径因为树中可能存在最长长度相等的多条简单路径。→推荐使用树形 DP 求解树的直径。● 根据树形 DP 法原理树的直径计算方法如下1路径定义‌树的直径是树中任意两节点间最长的简单路径长度。2状态转移‌以某节点为根的子树其延伸的最长路径长度记为d1次长路径长度记为d2。树的直径即为所有节点d1d2的最大值。3路径特性‌最长路径 d1 和次长路径 d2 无公共边确保路径唯一性。● 路径更新若 d1[j]1d1[u]说明通过 j 的路径更长更新 d1[u]d1[j]1同时旧的最长路径 d1[u] 转为次长路径 d2[u]。若 d1[j]1d1[u] 但 d1[j]1d2[u]说明 j 的路径虽非最长但比当前次长路径更长更新 d2[u]d1[j]1。● 更新方向在树形 DP 中路径长度从叶子节点无子节点开始计算逐层向上更新父节点的路径长度。因此j子节点确实会先于 u父节点被处理符合“自下向上更新”的描述。d1 和 d2 初始值为 0表示所有节点的最长和次长路径长度从 0 开始计算符合树形 DP 的初始化要求。​​​​​​​【算法代码一无权边】#include bits/stdc.h using namespace std; const int N1e55; int e[N1],ne[N1],h[N],idx; int d1[N],d2[N]; int imaxINT_MIN; void add(int a,int b) { e[idx]b,ne[idx]h[a],h[a]idx; } void dfs(int u,int fa) { for(int ih[u]; i!-1; ine[i]) { int je[i]; if(jfa) continue; dfs(j,u); if(d1[j]1d1[u]) { d2[u]d1[u]; d1[u]d1[j]1; } else if(d1[j]1d2[u]) { d2[u]d1[j]1; } } imaxmax(imax,d1[u]d2[u]); } int main() { memset(h,-1,sizeof h); int n; cinn; for(int i1; in; i) { int a,b; cinab; add(a,b),add(b,a); } dfs(1,-1); coutimaxendl; return 0; } /* in: 5 1 2 2 4 4 5 2 3 out: 3 */【算法代码二有权边】若边上有权代码如下所示。代码详见https://www.acwing.com/solution/content/287207/#include bits/stdc.h using namespace std; const int N1e55; int val[N1],e[N1],ne[N1],h[N],idx; int d1[N],d2[N]; int imaxINT_MIN; void add(int a,int b,int w) { val[idx]w,e[idx]b,ne[idx]h[a],h[a]idx; } void dfs(int u,int fa) { d1[u]d2[u]0; for(int ih[u]; i!-1; ine[i]) { int je[i]; if(jfa) continue; dfs(j,u); if(d1[j]val[i]d1[u]) { d2[u]d1[u]; d1[u]d1[j]val[i]; } else if(d1[j]val[i]d2[u]) { d2[u]d1[j]val[i]; } } imaxmax(imax,d1[u]d2[u]); } int main() { memset(h,-1,sizeof h); int n; cinn; for(int i1; in; i) { int a,b,w; cinabw; add(a,b,w),add(b,a,w); } dfs(1,-1); coutimaxendl; return 0; } /* in: 6 5 1 6 1 4 5 6 3 9 2 6 8 6 1 7 out: 22 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/140254954https://blog.csdn.net/hnjzsyjyj/article/details/140253125https://www.acwing.com/file_system/file/content/whole/index/content/12887532/https://www.luogu.com.cn/problem/B4016https://www.luogu.com.cn/problem/P3304https://blog.csdn.net/qq_39530733/article/details/141752520https://www.acwing.com/solution/content/63883/