题解：P5642 人造情感（emotion）

· · 题解

P5642

Part 1: 求 W(S)。

我们设 f_u 表示 u 子树内 W(S) 的最大值，g_u 表示 u 子树内不选 u 的 W(S) 的最大值。

那么首先有 g_u = \sum_{v \in son(u)} f_v。

* $u$ 不被路径经过，$f_u = g_u$。 * $u$ 被路径经过，枚举每条 $lca$ 在 $u$ 处的路径 $(x,y,w)$，考虑除开这条路径，计算这条路径所附带的子树的贡献，则 $f_u = \max\{w + \sum_{v \in path(x,y)} (g_v - \sum_{z \in next(v)} f_z)\}$，其中 $next(v)$ 表示 $v$ 在路径上的儿子，化简得 $f_u = \max \{ g_u + w + \sum_{v \in path(x,y), v \ne u} g_v - f_v \}$ 。 可以用 树链剖分+树状数组 做到 $O(n \log^2 n)

但是还不够优，可以令树状数组 val_u 表示 \sum_{v \in path(1,u)} g_u-f_u，相当于树上前缀和，至于修改时则使 u 子树内的 val_v = val_v + g_u-f_v，可以对树状数组差分，即可做到 O(n \log n)。

Part 2: 求单个 F(u,v)。

观察 W(U \cup \{(u, v, w + 1)\}) > W(U) 的条件，发现是相当于 (u,v) 的路径的权值是 w 时，要求此路径必选。仿照求 f 的思路，我们可以钦定这条路径要选，则令 h_u 表示 u 子树外的 W(S) 的最大值，那么有

h_{lca} + g_{lca} + \sum_{k \in path(u,v), k \ne lca} g_k-f_k + F(u,v) = f_1

移项得

F(u,v) = f_1 - h_{lca} - f_{lca} - \sum_{k \in path(u,v)} g_k-f_k

Part 3: 求 h_u。

依然仿照求 f 的思路，不过求 h_u 需要换根 dp。

令 v 为 u 的一个儿子，现在求 h_v，则我们新加了 u 除 v 的儿子的子树部分，可以分两种情况考虑。

第二种情况非常不好统计，考虑再分情况，观察一下发现又可分情况。

我们考虑能否把一层线段树去掉，也就是降维，这里考虑把端点在 u 祖先的其它子树中的降去，则需考虑每次 dfs 到 (u,v) 时，我们查询的一个端点一定在 u 的非 v 子树的路径都是合法的。

首先，我们必须把 lca 为 u 的祖先的路径加入线段树，我们如果算完 f_v 后就把 lca 为 v 的贡献加入，那么查询 u 其他子树时就有问题，考虑算完所有 h_v 后把 lca 为 u 的贡献加入，然后统一 dfs(v)，这样是正确的，因为 u 更新 v 的任务完成了我们才加入线段树，即使他不在另一个点 k 的祖先上，那么也不会查到它。这样时间复杂度和空间复杂度都是 O(n \log n)。

Part 4: 求所有 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)。