Part 1: 求 W ( S ) W(S) W ( S ) 我们设
f u f_u f u 表示
u u u 子树内
W ( S ) W(S) W ( S ) 的最大值，
g u g_u g u 表示
u u u 子树内不选
u u u 的
W ( S ) W(S) W ( S ) 的最大值。
那么首先有
g u = ∑ v ∈ s o n ( u ) f v g_u = \sum_{v \in son(u)} f_v g u = ∑ v ∈ so n ( u ) f v 。
u u u f u = g u f_u = g_u f u = g u u u u l c a lca l c a u u u ( x , y , w ) (x,y,w) ( x , y , w ) f u = max { w + ∑ v ∈ p a t h ( x , y ) ( g v − ∑ z ∈ n e x t ( v ) f z ) } f_u = \max\{w + \sum_{v \in path(x,y)} (g_v - \sum_{z \in next(v)} f_z)\} f u = max { w + ∑ v ∈ p a t h ( x , y ) ( g v − ∑ z ∈ n e x t ( v ) f z )} n e x t ( v ) next(v) n e x t ( v ) v v v f u = max { g u + w + ∑ v ∈ p a t h ( x , y ) , v ≠ u g v − f v } f_u = \max \{ g_u + w + \sum_{v \in path(x,y), v \ne u} g_v - f_v \} f u = max { g u + w + ∑ v ∈ p a t h ( x , y ) , v = u g v − f v }
可以用 树链剖分+树状数组 做到
O ( n log 2 n ) O(n \log^2 n) O ( n log 2 n )
但是还不够优，可以令树状数组
v a l u val_u v a l u 表示
∑ v ∈ p a t h ( 1 , u ) g u − f u \sum_{v \in path(1,u)} g_u-f_u ∑ v ∈ p a t h ( 1 , u ) g u − f u ，相当于树上前缀和，至于修改时则使
u u u 子树内的
v a l v = v a l v + g u − f v val_v = val_v + g_u-f_v v a l v = v a l v + g u − f v ，可以对树状数组差分，即可做到
O ( n log n ) O(n \log n) O ( n log n ) 。
Part 2: 求单个 F ( u , v ) F(u,v) F ( u , v ) 观察
W ( U ∪ { ( u , v , w + 1 ) } ) > W ( U ) W(U \cup \{(u, v, w + 1)\}) > W(U) W ( U ∪ {( u , v , w + 1 )}) > W ( U ) 的条件，发现是相当于
( u , v ) (u,v) ( u , v ) 的路径的权值是
w w w 时，要求此路径必选。仿照求
f f f 的思路，我们可以钦定这条路径要选，则令
h u h_u h u 表示
u u u 子树外的
W ( S ) W(S) W ( S ) 的最大值，那么有
h l c a + g l c a + ∑ k ∈ p a t h ( u , v ) , k ≠ l c a g k − h k + F ( u , v ) = f 1 h_{lca} + g_{lca} + \sum_{k \in path(u,v), k \ne lca} g_k-h_k + F(u,v) = f_1 h l c a + g l c a + ∑ k ∈ p a t h ( u , v ) , k = l c a g k − h k + F ( u , v ) = f 1 移项得
F ( u , v ) = f 1 − h l c a − f l c a − ∑ k ∈ p a t h ( u , v ) g k − h k F(u,v) = f_1 - h_{lca} - f_{lca} - \sum_{k \in path(u,v)} g_k-h_k F ( u , v ) = f 1 − h l c a − f l c a − ∑ k ∈ p a t h ( u , v ) g k − h k Part 3: 求 h u h_u h u 依然仿照求
f f f 的思路，不过求
h u h_u h u 需要换根 dp。
令
v v v 为
u u u 的一个儿子，现在求
h v h_v h v ，则我们新加了
u u u 除
v v v 的儿子的子树部分，可以分两种情况考虑。
没有路径经过 u u u h v = h u + g u − f v h_v = h_u + g_u - f_v h v = h u + g u − f v
有路径经过 u u u u u u v v v ( x , y , w ) (x,y,w) ( x , y , w ) h u = max { − f v + h l c a + g l c a + w + ∑ k ∈ p a t h ( u , v ) , k ≠ l c a g k − h k } h_u = \max \{-f_v + h_{lca} + g_{lca} + w + \sum_{k \in path(u,v), k \ne lca} g_k-h_k \} h u = max { − f v + h l c a + g l c a + w + ∑ k ∈ p a t h ( u , v ) , k = l c a g k − h k }
第二种情况非常不好统计，考虑再分情况，观察一下发现又可分情况。
l c a = u lca = u l c a = u O ( n m ) O(nm) O ( nm ) O ( n ) O(n) O ( n ) l c a ≠ u lca \ne u l c a = u u u u v v v u u u 96 p t s 96 pts 96 pt s
我们考虑能否把一层线段树去掉，也就是降维，这里考虑把端点在
u u u 祖先的其它子树中的降去，则需考虑每次 dfs 到
( u , v ) (u,v) ( u , v ) 时，我们查询的一个端点一定在
u u u 的非
v v v 子树的路径都是合法的。
首先，我们必须把
l c a lca l c a 为
u u u 的祖先的路径加入线段树，我们如果算完
f v f_v f v 后就把 lca 为
v v v 的贡献加入，那么查询
u u u 其他子树时就有问题，考虑算完所有
h v h_v h v 后把 lca 为
u u u 的贡献加入，然后统一
d f s ( v ) dfs(v) df s ( v ) ，这样是正确的，因为
u u u 更新
v v v 的任务完成了我们才加入线段树，即使他不在另一个点
k k k 的祖先上，那么也不会查到它。这样时间复杂度和空间复杂度都是
O ( n log n ) O(n \log n) O ( n log n ) 。
Part 4: 求所有 F ( u , v ) F(u,v) F ( u , v ) &= n^2 \times f_1 - \sum_{i=1}^{n} (p_i \times (h_i + f_i) + q_i \times (g_i - f_i))
\end{aligned}$$
其中 $p_i$ 表示 lca 为 $i$ 的路径数量，$q_i$ 表示经过 $i$ 的路径数量，dfs 时计算即可。
总时间复杂度 $O(n \log n)$。 
P5642