A. Luogu-P9058 Ynoi 2004 rpmtdq
解密：Range Pair Mininum Tree Distance Query
支配对问题，这里的支配是若 \(L\le l<r\le R\)，且 \(\mathrm{dist}(l,r)\le \mathrm{dist}(L,R)\)，那么 \((l,r)\) 支配 \([L,R]\)。
考虑点分治，在过程中对每个分治中心 \(ct\) 以及节点 \(i,j\)，默认 \(\mathrm{dist}(ct,i)\le \mathrm{dist}(ct,j)\)。此时找到 \(j\) 前后第一个满足这样条件的 \(i\) 就行了，发现对于其他的 \(i'<i<j\)，且 \(\mathrm{dist}(ct,i')\)，那么 \(\mathrm{i',i}\le \mathrm{i',j}\)，那么 \((i',j)\) 一定不在支配集。虽然这个判定条件很松，但作为必要条件且每次只会贡献 \(O(1)\) 个支配对，剩下就可以二维偏序求解了。
时间复杂度 \(O(n\log^2 n+q\log n)\)。
提交记录：Submission - Luogu
C. CodeForces-757G Can Bash Save the Day? *3400
朴素想法是点分树然后数据结构维护，优化一下自然想到树上主席树，但是修改很困难。
问题在于修改要把每个版本都改掉，考虑操作的特殊性在于邻项交换，那么交换主席树的两维，以 \(p\) 为版本，点分树上节点线段树下标，这样每次修改只对 \([1,x]\) 这个前缀有影响，直接重新建一下就行了。时空复杂度都是 \(O(n\log^2 n)\)。
上面这个做法是卡不过去的，所以等我学完边分树回来写能过的好做法。
H. Luogu-P5904 POI 2014 HOT-Hotels 加强版
这类的三元组有两种：\(\mathrm{LCA}\) 是或不是重心的。
先考虑朴素 DP 怎么做，我们希望问题在子树内解决，所以要在 \(\mathrm{LCA}\) 处统计答案。
对于第一种情况，设 \(f_{u,d}\) 为 \(u\) 子树内距离为 \(d\) 的节点个数，\(g_{u,d}\) 为 \(u\) 子树内到 \(u\) 距离均为 \(d\) 且 \(\mathrm{LCA}\) 为 \(u\) 的点对数。
枚举每棵子树以及距离，统计答案的过程：
\[g_{u,d+1}\times f_{v,d}\to \mathrm{ans} \]\[f_{u,d+1}\times f_{v,d}\to g_{u,d+1} \]\[f_{v,d}\to f_{u,d+1} \]对于第二种情况，设目标三元组 \((u,v,w)\)，有三部分组成：\(\mathrm{LCA}(u,v)\) 到 \(u,v\) 距离相等，均为 \(d_1\)，\(\mathrm{LCA}(u,v,w)\) 到 \(w\) 的距离 \(d_2\) 与到 \(\mathrm{LCA}(u,v)\) 的距离 \(d_3\) 无边集交且满足 \(d_1=d_2+d_3\)。
因为在 \(\mathrm{LCA}(u,v,w)\) 处统计答案，发现 \(d_3=d_1-d_2\)，因此 \(d_1-d_2\) 相等的位置本质没有区别，设 \(h_{u,d}\) 为 \(u\) 子树内满足这样情况且 \(d_1-d_2=d\) 的点对数，那么转移也类似上面了。
考虑怎么优化。
\(g\) 是只对一棵子树有效的，不需要继承，\(f\) 比较朴素的继承即可，而 \(h\) 比较不同，考虑到 \(v\) 到 \(u\) 后，\(d_1\) 不变而 \(d_2\) 增加 \(1\)，因此继承是形如 \(h_{v,d}\to h_{u,d-1}\)，与正常的继承不同。这就需要我们预处理指针时，把重儿子的指针设为父亲的指针减 \(1\)，从而空间要开 \(2\) 倍。
统计答案也需要精细处理，一个简单的想法是先计算轻子树之间的答案，这部分照搬暴力即可，同时要用一个临时数组记录一下当前统计到的 \(f,g,h\)。计算完之后，可以和重儿子继承来的 \(f,h\) 再合并得到另一部分的答案。
提交记录：Submission - Luogu
J. CodeForces-888G Xor-MST *2300
完全图二元函数最小生成树用 B 姓算法，两个树异或就建 01-Trie，那么在连最高位是 \(2^k\) 的边时，所有同属 \(2^k\) 子树的节点一定都连通了，那么就是两棵子树对应集合找一个最小异或和，启发式合并地选较小的一个暴力去 01-Trie 查询。时间复杂度 \(O(n\log n\log V)\)。
M. Luogu-P6976 NEERC2015 Distance on Triangulation
实际上是一个三角形剖分，形成了一个平面图。
发现可以选择一条边 \((u,v)\)，分别对当前的图 BFS 求 \(u\) 和 \(v\) 的单源最短路，那么此时所有端点在 \((u,v)\) 两侧的询问一定要经过 \(u,v\) 至少一个端点，那么就可以处理跨过的询问了，这个过程类似分治，所以要求尽量选择“重心”的一条边。
平面图转成对偶图，这样形成一棵树，发现点分治的过程就找到了重心。
实现比较困难，我还没实现出来。
标签：12,log,乱写,Luogu,分治,省选,答案,LCA,mathrm From： https://www.cnblogs.com/SoyTony/p/Tree_Training_Problems_of_Provincial_Team_Selection_in_B