【题解】Solution Set - NOIP2024集训Day12 树上启发式合并
https://www.becoder.com.cn/contest/5472
「CF600E」Lomsat gelral
直接 dsu on tree。记录每一个颜色的出现次数。
「IOI2011」Race
之前是用点分治做的。
考虑 dsu on tree。每个子树内维护到根节点的距离为 \(x\) 的最短条数（就是最小深度。
然后加入轻儿子的时候更新当前答案就行了。
因为我们优先计算轻儿子的答案，所以在清空当前子树的影响的时候，可以直接全部清除。
「CF375D」Tree and Queries
比较暴力的两只 \(\log\) 的 dsu on tree 做法，是再用一个线段树维护每个 \(cnt\) 有多少个。
线段树合并的做法，就是再用一个线段树维护 \(cnt\)，这样就做到了单 \(\log\)。
现在再来仔细想一想单 \(\log\) 的 dsu on tree 的做法。
考虑到每次 \(cnt\) 最多只会 \(\pm 1\)，我们就可以 \(O(1)\) 维护大于等于 \(k\) 的个数有多少个。
「CF715C」Digit Tree
一眼推式子题。（下面的运算都在模 \(m\) 的意义下进行。
\[\sum_{i=1}^{len} w_i\times 10^i\equiv 0\pmod m \]还是 不太好做。
标签：10,Set,dep,题解,dsu,tree,Solution,times,查询 From： https://www.cnblogs.com/CloudWings/p/18372439