24.10.16
A
算一个区间选两端点的贡献，可以二分出从哪里往左，哪里往右，然后前缀和后缀和搞一下。
然后得到了 \(O(n^2k)\) 的做法。然后猜一下决策单调性，打表发现每一层真的有决策单调性。
然后人类智慧维护决策点每次往后取随机数 \(\bmod 200\) 个更新决策点就过了。
然后经典二分+单调队列优化决策单调性。怎么不卡常我还 T 了。
B
费用递增模型。
首先经典的黑白染色。
然后每种颜色的点再分别按行的奇偶性红蓝染色。
把每个点拆成 3 个，\(x0\) 连 \(S\) 或 \(T\)，\(x1\) 连红点，\(x2\) 连蓝点。
若一个点度数为 \(k\)，那么它贡献了 \(\dfrac{k(k - 1)}{2}\) 个收费图案，然后直线会额外多 \(B - A\) 的花费。
- \(x0\) 和 \(S\) 或 \(T\) 连 \((1, kA), k \in [0, 3]\) 的边。
- \(x0\) 和 $ x1$ 和 \(x2\) 连 \((1, k(B - A)), k\in[0, 1]\) 的边。
费用流，每次多流 1 流量。
C
拆贡献
\[\begin{aligned}
\sum_{i = l}^r \operatorname{dis}(x, i)
&= \sum_{i = l}^r (\operatorname{dis}(1, x) + \operatorname{dis}(1, i) - 2\operatorname{dis}(1, \operatorname{lca}(x, i))) \\
&= (r - l + 1)\operatorname{dis}(1, x) + \sum_{i = l}^r\operatorname{dis}(1, i) - \sum_{i = l}^r2\operatorname{dis}(1, \operatorname{lca}(x, i))
\end{aligned}
\]
对于减号后面一部分可以参考 [[LNOI2014] LCA](https://www.luogu.com.cn/problem/P4211)。
分块维护，对于第一部分可以树剖维护每个点到根的距离。
第二第三部分处理块内所有点到 \(1\) 的距离和每个点在当前块像 [LNOI2014] LCA 处理后的树上到 \(1\) 的距离。
边权转点权，预处理 \(s_{id, x}\) 记录 \(x\) 子树里有多少 \(id\) 块内的点，那么更改 \(x\) 的点权对 \(id\) 块就会影响 \(s_{id, x}\) 个点到根的距离以及子树内每个点到 \(1\) 的距离。
所以每个块树状用树状数组维护第三部分子树加单点查询。