先考虑求 W(S)。
有一个线性规划对偶然后贪心的解释，不过大概和以下做法本质是一样的。
设 f′u 为考虑 u 子树内的路径的答案，则有转移 f′u=max{∑v∈child(u)f′v}⋃{w+∑fa(v)∈path(x,y)∧v∉path(x,y)f′v|(x,y,w)∈S∧lca(x,y)=u}
这样的转移很阴间。不过这样的对「路径下方所挂的点」的求和，提示我们作树上差分。
设 fu=f′u−∑v∈child(u)f′v
这样，不难验证转移会变成 fu=max{0}⋃{w−∑fa(v)∈path(x,y)∖{u}fv|(x,y,w)∈S∧lca(x,y)=u}
于是可以使用树状数组维护单点加链求和来做到 O((n+m)logn)。
接下来考虑计算 f(x,y)。观察到，若树的根在 path(x,y) 上，那么 f(x,y)=∑u∈path(x,y)fu
也就是说问题变成了换根 DP。
设 gu 为根在 u 子树内时 fa(u) 的 DP 值，hu 为根为 u 时 u 的 DP 值。
计算 gu 时，考虑一条经过 fa(u) 而不经过 u 的路径 (x,y,w)，从 fa(u) 出发向下的一段取 f，fa(u) 到 lca(x,y) 的一段取 g，lca(x,y) 往下的另一段也取 f。
计算 hu 时类似，不过考虑的是经过 u 的路径。
考虑继续在 u 处枚举 lca(x,y)=u 的路径 (x,y,w)，我们希望对路径上的点都挂上一个贡献，同时 u 处要特殊处理，因为有儿子的要求。
进一步，对于 u 枚举 v∈child(u)，考虑端点在 u 子树内而不在 v 子树内的路径，这样的路径就是对 gv 有贡献的。对于 hu 则更简单。
于是我们不妨用线段树维护 DFS 序来计算这部分转移。
u 处的特殊贡献的话，也可以直接对所有儿子建立线段树（或者如果足够闲，甚至可以通过差分和堆计算），这样不转移 O(1) 个儿子可以转化为对 O(1) 个区间取 max，然后单点查询。
时间复杂度 O((n+m)logn)。
代码：
1 |
|