树上的一些基础操作

树的直径

树的直径就是树上最远两点间简单路径的距离，也就是树上最长的简单路径。

可以用 树形 dp 的思想做

考察树上任意节点 u，若它有 i 条子树，则就有 i 条过 u 点（严格是以 u 为端点）的路径，要找到 悬挂 在 u 点的最长路径，贪心地想就是找到 最长路径 和 次长路径 合起来就是过 u 点的可能解

设 d1，d2 分别表示最长路径，次长路径，边界肯定就是 0（只有该点）

对于 (u, v) 方向上的子树路径长度 d，可以递推求解

• d > d1，则 d2 = d1, d1 = d
• d > d2，则 d2 = d

结果就是对所有点的最长路径取最大值 \(\max\limits_{i\in V}\{d1_i + d2_i\}\)，复杂度 \(O(n)\)

int dfs(int u, int fa)
{
	int d1 = 0, d2 = 0;
	
	for (re i = h[u]; i; i = e[i].next)
	{
		int v = e[i].to, w = e[i].w;
		if (v == fa) continue;
		
		int d = dfs(v, u) + w;
		if (d > d1) d2 = d1, d1 = d;
		else if (d > d2) d2 = d;
	}
	res = max(res, d1 + d2);
	
	return d1;
}