树的直径

[sshwy]

https://oi-wiki.org/graph/tree-diameter/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[YOYO-UIAT]

能把代码里的宏定义去掉吗，感觉好难看懂啊

[ShiChenbin]

@YOYO-UIAT
能把代码里的宏定义去掉吗，感觉好难看懂啊

盲猜这是xiaodao的宏定义

[AMIRIOX]

所以这些宏定义是怎么定义的...RD， PB都是啥啊/yiw

[AccRobin]

补充一下：两次DFS的方法不适用于有负权边的树

[KisaragiAkari]

bfs也能求吧，虽然与dfs思路相同

[liuziao20081122]

没有别的例题吗

[Bzdhxs-nt]

这个...dfs的证明是不是错了啊..

[NFLSCode]

@yozora0908
bfs也能求吧，虽然与dfs思路相同

就是求出距离某一个点最远的点就行了，显然dfs最方便

[minghu6]

没看出树形dp的实现和“dp”这个概念有什么关系？

[jinfuchiang]

两次DFS的反证法的第三种情况： $y$ 不在 $\delta(s,t)$ 上，且 $\delta(y,z)$ 与 $\delta(s,t)$ 不存在重合路径中， $\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x',z) > \delta(x',t)$ 这一步如果要成立，须要求点 $x'$ 既在 $\delta(y,z)$ 又在 $\delta(y,t)$ 上，然而目前的证明并未证出一定存在满足该条件的点 $x'$ 。

[Zewbiee]

这种情况 $x'$ 的位置可能有两种情况：一种是如图所示的 $yz$ 之间，另一种是在 $zy$ 的延长线上，不难证明对第二种情况也满足 $\delta(y,z)>\delta(y,t)\Longrightarrow\delta(x',z)>\delta(x',t)$.

[jinfuchiang]

噢，证明的设定应该是 $x'$ 就在 $\delta(y,t)$ 上，然后对 $x'$ 在 $\delta(y,z)$ 或不在 $\delta(y,z)$ 的情形都满足 $\delta(x',z) > \delta(x',t)$。Thanks♪(･ω･)ﾉ

[widsnoy]

void dfs(int u, int fa) {
	for (int v : G[u]) if (v != fa) {
		dfs(v, u);
		res = max(res, dp[u] + 1 + dp[v]);
		dp[u] = max(dp[u], dp[v] + 1);
	}
} 

可以用 $dp[u]$ 表示到子树中最远叶子的距离, 这样做树形 DP 更好写.

[Skymore]

这个方法看起来不对。
计算完dfs(v, u)后，更新res需要用不经过v的dp[u]和dp[v]来计算，而此时dp[u]是没有计算完的（u的其他节点会更新dp[u]）。

[T55AMD]

这个反证法的证明对我来说理解起来可能没有那么形象、直观，我想了想也许可以这么理解（大佬勿喷）：
第一次指定一个节点为根，然后第一次深搜找到深度最大的节点，然后再从这个节点深搜一次寻找到这个节点最远的节点，其实就是在找以根为起点的深度第二长的路径（两条路径加起来肯定是树上最长路径）。

[T55AMD]

哦，好像不太对。

[jerry-1-2-3]

大佬们教教dp算直径怎么找到直径的端点

[BlueSuryxin]

有几个问题：这里的fa是什么意思，节点是从0开始吗，为什么是i<n。