brain

Problem

给定一棵以 \(1\) 为根的树，给定树上所有点权与边权。

记 \(d(i, j)\) 表示 \(i\) 到 \(j\) 的路径长度。定义一棵树的权值为：

\[\sum\limits_{i = 1}^{n - 1}\sum\limits_{j = i + 1}^{n}a_{i}a_{j}d(i, j) \]

定义一次对点 \(i\) 的改造操作为：

删掉 \(i\) 与其父节点相连的边，并选择子树 \(i\) 内的一个点 \(x\)（\(x\) 可以为 \(i\) 本身），将 \(x\) 与 \(i\) 的父节点相连，形成一棵新树。

对点 \(i \in [2, n]\)，求出对 \(i\) 改造后树权值的最大值。

Solution

求出原树的权值是容易的。

考虑对每个操作计算其 变化量 并取其最值。

对点 \(i\) 进行改造操作，记 \(T_1\) 表示子树 \(i\)，\(T_2\) 表示原树去掉 \(T_1\) 后的连通块，考虑对变化量做贡献的只有那些不在同一连通块内的点对 \((p, q)\)。

以下记 \(a_i\) 表示点 \(i\) 的权值，\(s_i\) 表示子树 \(i\) 内的点权和，\(w_i\) 表示 \(i\) 与父节点连边的边权。

对 \(T_1\) 内的任意点 \(x\) 作为新边的端点求出所有上述点对 \((p, q)\) 的代价，以便分析 \(x\) 变化时 这部分变化量的大小。

\[\begin{aligned} \sum\limits_{p \in T_1}\sum\limits_{q \in T_2}a_{p}a_{q}d(p, q) &= \sum\limits_{p \in T_1}\sum\limits_{q \in T_2}a_{p}a_{q}(d(p, x) + d(x, q)) \\ &= \sum\limits_{q \in T_2}a_{q}\sum\limits_{p \in T_1}a_{p}d(p, x) + \sum\limits_{p \in T_1}a_{p}\sum\limits_{q \in T_2}a_{q}d(x, q) \end{aligned} \]

注意 \(x\) 是变量，因此后面的式子是定值，只有前面的 \(\sum\limits_{p \in T_1}a_{p}d(p, x)\) 是关于 \(x\) 变化的。

再强调一遍，这里是对不同的 \(x\) 考察已经重连边后我们指定的点对的贡献值是否变化，而不是固定死 \(x\)，考察改造前后的贡献值怎样变化。原题解正是在这里没有想清楚，导致定值与变化的量恰好搞反了，~~真是害人不浅~~。

那我们不是要算改造前后的变化量吗？是要，没错，但如果你固定死 \(x\) 去考察，你就要枚举 \(x\)，而这是时间复杂度不允许的。

但如果你对子树 \(i\) 内的每个 \(x\) 算出改造后的点对贡献值，你只需再减去原贡献值就可以得出变化量，并且你有机会在一个较为优秀的时间复杂度内解决变化量的最值问题。

好，现在考察 \(\sum\limits_{p \in T_1}a_{p}d(p, x)\) 的变化量。

思考重连边对子树 \(i\) 内影响的实质是什么？换根。

把 \(d(p, x)\) 拆到边权上进行考虑，发现只有在 \(i\) 到 \(x\) 的路径上的边对变化量做贡献。变化量要从 “增量”（新算 \(p \to x\) 的贡献）与 “减量”（减掉 \(p \to i\) 的贡献）分别考虑。具体地，可以如下表示出变化量：

\[\begin{aligned} &\,\,\,\,\,\,\,\, \sum\limits_{j \in Path(i \to x), j \neq i}w_j\times (s_i - s_j) - \sum\limits_{j \in Path(i \to x), j \neq i}w_j \times s_j \\ &= \sum\limits_{j \in Path(i \to x), j \neq i}w_j\times (s_i - 2s_j) \end{aligned} \]

这个 \(Path(i \to x)\) 太难看了，显然可以用前缀和表示。

记 \(l_i\) 表示 \(i \to 1\) 的边权和，\(c_i\) 表示 \(i \to 1\) 路径上 \(s_jw_j\) 之和（这里的所有变量名都和原题解一致）。化简上述变化量：

\[\begin{aligned} \sum\limits_{j \in Path(i \to x), j \neq i}w_j\times (s_i - 2s_j) &= s_i\times (l_x - l_i) - 2(c_x - c_i) \\ &= (s_{i}l_{x} - 2c_{x}) + 2c_i - s_{i}l_{i} \end{aligned} \]

注意转化后括号里面是关于 \(x\) 的一次函数。这是什么？

李超线段树合并。完结撒花。

之后贴个代码。

牢骚：原题面将边权以 “他到他的父亲的边的边权为 \(w_i\)” 的方式给出。

本人以为树的形态改变后，一条边的权值会随着父子关系的变化而变化，遂爆零QWQ。