2024.10.16总结
本文于 github 博客同步更新。
A：
打表发现有决策单调性，考虑人类智慧，每次向后跳 \(rand\%200\) 个点，若更优则继续跳，然后就过了。
正解是这样写的：
设 \(p[i\)] 为当前层的最优决策点，把决策按顺序加入，同时更新 \(p[i]\) 把相同的 \(p[i]\) 合并成一个点，对这些点维护栈，每加入一个决策 \(k\) 就弹出一些栈顶并加入 \(p[i]=k\) 的点，区间长度可以二分 \(\mathcal O(log n)\) 求出比较两个决策的优劣可以用二分 \(\mathcal O(log n)\) 比较。
B：
黑白染色非常典，酱紫拆点没想到，回头得去看看类似的 trick。
首先正常黑白染色，然后对同色的点按行的奇偶再次红蓝染色，这样就可以把所有点分成四类。
考虑将一个点拆成 \(x,x_1,x_2\) 三个点，其中 \(x\) 连接 \(S/T\)，\(x_1,x_2\) 分别连接相邻的红/蓝点。
画个图：
（其中 A、D 与 B、C 相邻，A、D 为白点，B、C 为黑点，A、B 为红点，C、D 为蓝点）
先假设 \(A=B\) ，我们只考虑每个点以自己为中心产生的贡献，若该点度数为 \(k\) ，则其贡献为 \(A\times k\times (k-1)/2\)。
列出来就是 \(0,1,3,6\)，使用费用递增模型，向 \(S/T\) 连四条边：\((1,0)(1,A)(1,2A),(1,3A)\)。
不用上面的拆点，可以得到 52pts，现在继续考虑 \(A\neq B\) 的情况。
我们按照上边的染色方法染色后，发现对于一个点，它上下的点同色，左右的点同色，且上下与左右的点异色。
这样的图：
也就是说当 \(x\) 与 \(x_1/x_2\) 之间的边流量流完时，说明产生了一条直线，这这时贡献就需要加上 \(B-A\)。
还是费用递增模型，我们从 \(x\) 向 \(x_1,x_2\) 连两条边：\((1,0)(1,B-A)\)，这样就可以计算直线的贡献了。
时间复杂度 \(\mathcal O(n^2m^2)\)
C：
同样是按编号分块，考虑维护好每一块的答案。
考虑拆分，\(dis(a,b)=dis(1,a)+dis(1,b)-2*dis(1,lca(a,b))\)，只需维护好最后一个部分即可。
对于每一块，在树上 dfs 一遍，计算出 \(s[i]=\) 块内所有点到 1 的路径中，第 \(i\) 条边被覆盖的总次数。
同时对每个块维护 \(ans[i]=\) 点 \(i\) 到这个块中所有点的距离之和修改变为对每个块的 \(ans\) 进行子树加，查询变为对每个块单点查询 \(ans[x]\)。
对每个块维护一个树状数组即可，时间复杂度 \(\mathcal O(n\sqrt n\log n)\)。