【题目来源】
【题目描述】
树的直径指的是，树中两点之间的最长路径。现给定一棵树的数据，请问该树的直径的是多少？
比如，如图所示的树，直径应该是 3−2−5−6，路径长度为 3。
【输入格式】
第 1 行有一个整数 n，代表结点的数量，结点的编号为 1~n。（n≤100）
接下来有 n-1 行，每行有 2 个整数 x，y，表示结点 x 和 y 之间有一条边。（不保证 x 是 y 的父）
【输出格式】
输出一个整数 n 代表树的直径。
【输入样例】
6
1 2
3 2
5 6
2 4
5 2
【输出样例】
3
【数据范围】
n≤100
【算法分析】
● 什么是树的直径？树上任意两结点之间最长的简单路径即为树的直径。
若无负权边，可以采用两次 DFS 或者树形 DP 的方法在 O(n) 时间求出树的直径；若有负权边，则只能采用树形 DP 求解树的直径。显然，一棵树可以有多条直径，因为树中可能存在最长长度相等的多条简单路径。→ 推荐使用树形 DP 求解树的直径。
● 根据树形 DP 法原理，树的直径计算方法如下：
（1）路径定义：树的直径是树中任意两节点间最长的简单路径长度。
（2）状态转移：以某节点为根的子树，其延伸的最长路径长度记为 d1，次长路径长度记为 d2。树的直径即为所有节点 d1+d2 的最大值。
（3）路径特性：最长路径 d1 和次长路径 d2 无公共边，确保路径唯一性。
● 路径更新
若 d1[j]+1>d1[u]，说明通过 j 的路径更长，更新 d1[u]=d1[j]+1，同时旧的最长路径 d1[u] 转为次长路径 d2[u]。
若 d1[j]+1<=d1[u] 但 d1[j]+1>d2[u]，说明 j 的路径虽非最长，但比当前次长路径更长，更新 d2[u]=d1[j]+1。
● 更新方向
在树形 DP 中，路径长度从叶子节点（无子节点）开始计算，逐层向上更新父节点的路径长度。因此，j（子节点）确实会先于 u（父节点）被处理，符合“自下向上更新”的描述。
d1 和 d2 初始值为 0，表示所有节点的最长和次长路径长度从 0 开始计算，符合树形 DP 的初始化要求。
【算法代码】
本题代码与“洛谷 B4016：树的直径”（）完全一样。
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int e[N<<1],ne[N<<1],h[N],idx;
int d1[N],d2[N];
int imax=INT_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 i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(j==fa) continue;dfs(j,u);if(d1[j]+1>d1[u]) {d2[u]=d1[u];d1[u]=d1[j]+1;} else if(d1[j]+1>d2[u]) {d2[u]=d1[j]+1;}}imax=max(imax,d1[u]+d2[u]);
}int main() {memset(h,-1,sizeof h);int n;cin>>n;for(int i=1; i<n; i++) {int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1,-1);cout<<imax<<endl;return 0;
}/*
in:
6
1 2
3 2
5 6
2 4
5 2out:
3
*/
【参考文献】