CF1260F Colored Tree
题意
一颗有 n 个节点的树，每个节点 v 有颜色 $c_v$，这个染色方案的权值为 $\sum\limits_{u,v\in[1,n],v>u,c_v=c_u}\operatorname{dis}{(u,v)}$。
现在知道每个节点 v 可以染成 $[l_v,r_v]$ 中任意颜色，求所有染色方案的权值之和。
$n\le 10^5$，时限 2.5 秒。
思路
一个显然的想法是考虑每一条路径的贡献，于是自然的想到点分治。考虑过分治中心一条路径的贡献（为方便起见，后文都算的是权值期望）。
显然贡献为：
$$ (d_u+d_v)\frac{|[l_u,r_u]\cap[l_v,r_v]|}{|[l_u,r_u]|\cdot|[l_v,r_v]|} $$我们可以维护一个线段树，在搜到 u 的时，把 $[l_u,r_u]$ 区间加 $\frac{d_u}{\|[l_u,r_u]\|}$。搜到 v 时，把 $[l_v,r_v]$ 区间的和，乘以 $\frac1{\|[l_v,r_v]\|}$，加到答案里即可，这样我们就解决了上式中第一项。
对于第二项，可以反着做一遍，也可以再开一个另外含义的线段树，怎么搞都行。
复杂度 $\mathcal{O}(n\log^2 n)$。
题解提供了一个不用点分治的做法，复杂度一样，在此先不说，因为我没读懂。
代码
|
|
树上游戏
实在找不到啥点分治好题了，只能用点分治硬做这题。
题意
树上每个点有颜色，定义 $\operatorname{s}{(i,j)}$ 为 i 到 j 路径颜色数，对于 $i\in[1,n]$ 求 $ans_i=\sum\limits_{j\in[1,n]}\operatorname{s}{(i,j)}$。
$n\le10^5$，时限 1 秒。
思路
这题怎么做都行，有好多线性的做法，但是我们要有拿下最劣解的追求，为了实现这一目标，考虑淀粉质的做法。
上图中，蓝色大三角表示所有搜过的子树，v 是正在查询的点，对于所有过分治中心 rt 的路径 $u \sim v$，考虑红色对哪些路径有贡献，发现有两种情况：
- u 在某个红色节点的子树中
- $v \sim rt$ 上有红色节点
定义 hasc 表示（蓝色子树中）到 rt 的路径上有红色的点数，当我修改节点 u 的时候，如果发现路径 $rt\sim u$ 上没有红色的话，我就 $hasc\gets hasc + \text{u 子树大小}$。
在查询时,一开始的答案为 hasc ，dfs 的过程中，如果第一次碰到一个红色点（这个点的祖先上没有红色点），那么对于其子树，红色的贡献就增加了蓝色区域的点数，回溯的时候再撤销即可。
因为每个点只有一个颜色，所以其实上述的过程是可以在 dfs 中对每个颜色同时进行的。
复杂度 $O(n\log n)$。
有不少细节，尤其是在分治中心的处理上，不建议实现。
代码
|
|
P3060 [USACO12NOV]Balanced Trees G
题意
给出一棵树，每个节点上有一个括号，对于所有括号匹配的路径，求其嵌套层数最大值。
思路
括号匹配比较有用的性质就是把 { 看成 1，} 看成 -1，最终序列的前缀和 $pre_i$都大于等于 0，并且总和 s 为 0.
而最大嵌套层数则等于前缀和的最大值。
考虑把两个括号序列合起来：
$$ \begin{aligned} str&=str1 + str2\cr s&=s1+s2\cr \max{(pre_i)}&=\max{(\max{(pre1_i)},s1+\max{(pre2_i)})}\cr \min{(pre_i)}&=\min{(\min{(pre1_i)},s1+\min{(pre2_i)})} \end{aligned} $$所以只需在第一次 dfs 时，判断如果前半段 pre 的最小值大于等于 0，就把前半段 pre 的最大值打到一个桶里 s1 的位置，查询就随便搞搞即可。
没时间实现了，我妈催我睡觉😡。