分析
没脑子的题目。
一眼换根 DP。定义 \(\mathit{f}_{i}\) 表示 \(i\) 到 \(i\) 为根子树中某一个节点的距离最大值；\(\mathit{g}_{i}\) 表示 \(i\) 经过其父节点到某个节点的距离最大值。那答案就是 \(\max(\mathit{f}_i,\mathit{g}_i)\)。
考虑转移。\(\mathit{f}_i\) 的转移很简单，就是 \(\mathit{f}_{i} =\max\{\max(val_j,f_j)+w_k|i \to j\}\)。这里将 \(val_j\) 和 \(\mathit{f}_i\) 取最大值是因为会出现 \(j\) 是叶子节点的情况。求 \(\mathit{g}_i\) 的时候换根 DP 就行了。定义 \(\mathit{fa}_i\) 表示 \(i\) 的父亲节点。那么 \(\mathit{g}_i=\max(\max(val_{fa_i},g_{fa_i})+w_k,\max\{\max(val_j,f_j)+w_{k'}+w_k|fa_i \to j\land fa_i \to i\})\)。前半部分是由父亲直接转移的情况，后半部分是由与 \(i\) 同备份的节点转移的情况。用两个变量存最大值和次小值可以 \(O(n)\) 求出来，当然也是可以 \(O(n \log n)\) 用大根堆乱搞。
代码
Link.
标签：val,mathit,题解,最大值,fa,max,abc222,ABC222F,节点 From： https://www.cnblogs.com/harmisyz/p/18058649