P5642 人造感情

P5642 人造感情
首先考虑如何求 \(W(U)\)。
对于路径 \((x,y,w)\)，我们将它挂在 \(u=lca(x,y)\) 上，记 \(f_u\) 表示仅考虑 \(u\) 子树内的链获得的最大值，\(s_u=\sum_{v\in son_u}f_v\)，表示仅考虑 \(u\) 子树内的链，且钦定 \(u\) 不被占用的最大值。
\(s_u\) 易求，若 \(u\) 不被占用，\(f_u=s_u\)，否则枚举挂在 \(u\) 上的路径 \((x,y,w)\)，则 \(\text{path}(x,y)\) 上的点都不能被占用。
发现转移需要将下面图中的橙色子树 \(dp\) 值加起来：

发现其就是 \(s_u+\sum_{z\in \text{path}(x,y),z\neq u}s_z-f_z\)，因此 \(f_u=\max(s_u,w+s_u+\sum_{z\in \text{path}(x,y),z\neq u}s_z-f_z)\)
和式用 DFS 序+树状数组维护一个点到根节点的 \(s_u-f_u\) 的和。
那么 \(f_1\) 就是原始答案。
为了求后面的答案，我们需要多维护一个 \(dp\)：\(g_u\) 表示把 \(u\) 子树抛去后剩余部分的最大值。
在此之前，我们把所有路径的权值更新：\(w\leftarrow w+s_u+\sum_{z\in \text{path}(x,y),z\neq u}s_z-f_z\)，表示在强制选这条边的情况下 \(u\) 子树内的最大值。
现在假设 \(g_u\) 已求出，尝试递推出 \(g_v\)：
先更新挂在 \(u\) 节点上路径权值 \(w\leftarrow w+g_u\) 表示强制选这条边的情况下全局的最大值。

• \(u\) 未被占用，\(g_v\leftarrow g_u+s_u-f_v\)。
• \(u\) 被占用，且占用 \(u\) 的路径 \((x,y,w)\) 只有一个端点是 \(u\) 子树内的点（不能是 \(v\) 的后代），此时一定有 \(lca(x,y)\) 是 \(u\) 的祖先.
  \(g_v\leftarrow \max w-f_v\)。
• u 被占用，且占用 \(u\) 的路径 \((x,y,w)\) 两个端点都是 \(u\) 子树内的点（不能是 \(v\) 的后代），那么该路径一定是挂在 \(u\) 上的。
  \(g_v\leftarrow \max w -f_v\)

考虑如何找到情况2和情况3中的路径：
对于情况2，我们在一个点 \(u\) 更新完所有子节点后，在递归前把挂在 \(u\) 上的路径按照端点 DFS 序将权值插入线段树中，这样情况2就只需在线段树中查询端点落在指定区间的最大值即可。
对于情况3，先将路径从大到小排序，然后暴力找到第一条不占用 \(v\) 的路径，由于一条路径只占用2个子节点，所以对于所有子节点，一条路径被“无效访问”的次数最多为 \(2\)，因此暴力的复杂度是线性的。

在做了上述一堆准备工作后，现在考虑答案怎么求：
当插入一条路径 \((u,v)\) 后，将 \(\text{path}(u,v)\) 上的点都断开，然后将剩余连通块的最大值加起来，记为 \(val\)，\(f_1-val\) 即为 \(f(u,v)\)。
对于上述中的连通块，它要么是一个子树，要么是原树剖去一个子树，分别对应之前求出的 \(f_u,g_u\)。

考虑对于每个节点 \(u\)，统计 \(f_u\) 与 \(g_u\) 被计算的次数。

一条路径会算到 \(f_u\) 当且仅当 \(u\) 的父亲被经过而 \(u\) 不被经过，会算到 \(g_u\) 当且仅当 \(u\) 被经过而 \(u\) 的父亲不被经过，容斥计算上述的路径条数即可。

时间复杂度 \(\mathcal{O}(n\log n)\)。