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\times dis(1,lca(a,b))$，只需维护好最后一个部分即可。

对于每一块，在树上 dfs 一遍，计算出 $s[i]=$ 块内所有点到 1 的路径中，第 $i$ 条边被覆盖的总次数。

同时对每个块维护 $ans[i]=$ 点 $i$ 到这个块中所有点的距离之和修改变为对每个块的 $ans$ 进行子树加，查询变为对每个块单点查询 $ans[x]$。

对每个块维护一个树状数组即可，时间复杂度 $\mathcal O(n\sqrt n\log n)$。