luogu_gza @ 2024-03-10 11:02:14
这样的做法有点讨论区博客，但请见谅，我想让更多人看到这个。
平时各位求树的直径的时候通常使用的是两遍 dfs，但是这个算法在负权边时可以被卡掉。
下面的数据就可以：
5
1 2 100
1 3 -100
3 4 -100
4 5 200 两遍 dfs 程序一般会输出 100（假如你第一遍 dfs 的起点不是 5 的话）。
而求一个点往下的最长链和次长链做法会输出 200，这是正确的答案。
今天给人调题的时候刚刚发现的。
请勿喷，这是一位初二老年选手非常激动的发现。
by xiaosi4081 @ 2024-03-10 11:03:53
负权边确实不能用两次 dfs 啊，要用 dp
by TsinghuaMeng @ 2024-03-10 11:06:25
@luogu_gza 额， dfs 不能算负权边不是常识？
by luogu_gza @ 2024-03-10 11:07:17
@Hot_tear 我从来不知道这件事情/sad
by Accelessar @ 2024-03-10 11:09:41
其实 oiwiki 上特地强调了这个的（
by rui_er @ 2024-03-10 11:12:13
两次 dfs 不能用于负权边，这个是我学直径的时候就知道的（）
by luogu_gza @ 2024-03-10 11:13:34
再者，“离某个点最远的点一定是直径断电”这个性质貌似也没了！