标签：emotion 子树 子树内 limits P5642 人造 权值 sum

P5642 人造情感（emotion）

洛谷：P5642 人造情感（emotion）

Solution

子问题：HDU5293 Tree chain problem

这里直接把 之前写的题解 复制过来QWQ

考虑 dp。把链的信息挂在深度最浅的节点上，自下而上更新答案。

记 \(f_u\) 表示 \(u\) 子树内的最大权值和，\(S\) 表示挂在 \(u\) 上的某条链，\(son(x)\) 表示点 \(x\) 的儿子集合，\(T_u\) 表示子树 \(u\) 的点集。

则 \(f_u\) 的初始值为：

\[f_u = \sum\limits_{v \in son(u)}f_{v} \]

考虑加链的转移为：

\[\begin{aligned} f_u &= \max\left( \sum\limits_{x \in T_u, x \not\in S}f_{x} + w_S \right) \\ &= \max\left( \left(\sum\limits_{x \in S}\sum\limits_{v \in son(x)}f_{v} \right) - \sum\limits_{x \in S, x \neq u}f_{x} + w_S \right) \\ \end{aligned} \]

观察发现双重和式中的内层可以在之前的更新中处理出来，即记 \(sum_u\) 表示 \(\sum\limits_{v \in son(u)}f_{v}\)。

把 \(sum - f\) 看成整体处理，考虑维护一个点到根节点的 \(sum - f\) 的权值和，修改时对子树 \(u\) 内的节点都加上 \(sum_u - f_{u}\) 的贡献，子树恰好是一个连续的 dfn 序；查询时单点查询。

树状数组维护可以 \(O(n\log{n})\) 静态求 \(W(U)\)。

现在要钦定某条链被锁定，考察抛开该条链（即该条链中的点都不选）后其他部分的 \(W(U)\) 的权值。

对于横跨根节点的链，可以直接在树状数组上查询剩余子树的 \(f\) 之和。

否则，对于一条端点 lca 为 \(x\) 的链，则要在树状数组上查询 \(x\) 子树内抛开链后剩余子树的和 与 抛开 \(x\) 子树后剩余部分的最大权值。

我们记 \(g_x\) 表示抛开 \(x\) 子树后剩余部分的最大权值。

考虑从 \(g_u\) 转移到 \(g_v\)，其中 \(u\) 为 \(v\) 的父节点。

• 假设不占用点 \(u\)，\(g_v \leftarrow g_u + sum_u - f_v\)。

• 假设占用点 \(u\)，且占用点 \(u\) 的链 \(S\) 所挂的点（即端点的 lca）为 \(p\)，则 \(g_v \leftarrow g_p + \sum\limits_{x \in S}sum_x - \sum\limits_{x \in S, x \neq p}f_{x} + w_S - f_v\)。

  枚举链 \(S\)，找所有情况中后面那坨的最大值赋给 \(g_v\)。

  为方便表示以及减小常数，不妨把 \(w_S\) 初始成 \(\sum\limits_{x \in S}sum_x - \sum\limits_{x \in S, x \neq p}f_{x} + w_S\)，在处理 \(g\) 数组的 dfs 过程中，再随时更新 \(w_S \leftarrow w_S + g_p\)。对于当前的 \(u, v\) 转移，\(g_v \leftarrow \max(w_S - f_v)\)。

  现在问题在于枚举 \(S\)：我们只需要找到变形后的 \(w\) 值最大的链，且该链穿过 \(u\) 但不经过 \(v\) 子树。这里又要分类处理：

  • 若 \(S\) 一端在 \(u\) 子树内，一端在 \(u\) 子树外，可用线段树维护基于 dfs 序的区间最大值。
  • 若 \(S\) 两端均在 \(u\) 子树内，可以排序后暴力枚举 \(S\)，考虑每条链无效（即端点落在 \(v\) 子树内）的次数最多为 \(2\) 次，因此仅考虑枚举的复杂度是线性的。（注意找到最大的链后直接 break 啊）

以上求出了 \(g\) 的值后，易得一个 \(O(n^2\log{n})\) 的暴力，即枚举每条链，用全局最大值 \(f_1\) 减去去掉链上点的部分的最大值 \(val\)。

正解为直接利用 \(f, g\)，统计每个点的 \(f, g\) 被多少条链计算到 \(val\) 中去，记所有的这部分权值和为 \(sval\)。分类讨论组合计数，不难。

易得答案为 \(n^2\times f_1 - sval\)。

code 人造情感（emotion）

标签：emotion,子树,子树内,limits,P5642,人造,权值,sum
From： https://www.cnblogs.com/Schucking-Sattin/p/17494367.html