要退役做一些自己感觉好久没做过或者没学过的题。
P6626 [省选联考 2020 B 卷] 消息传递
套路点分治，把询问挂在点上，然后就是每次处理跨越重心的路径，贡献到目前的每个点上。
P2664 树上游戏
对颜色进行计数，乍一看不可做，但是经过推导之后发现可以直接上点分，路径贡献到点上，差分，用 dfs 去除一些多余颜色贡献。
CF715C Digit Tree
不想多说，煞笔至极，直接记模 \(M\) 余数，然后一个数的后半段匹配前半段，正好要 \(10\) 的逆元。
P4075 [SDOI2016] 模式字符串
上点分，中间一段显然用哈希，其他完全是 \(S\) 的部分直接 DFS 记录 \(|S|\) 级父亲到这里是否合法即可，记录祖先哈希就行。不想写了。
P2305 [NOI2014] 购票
写几个做法。
第一个是有根树点分。先处理根的子树，然后剩下子树就是这个分治中心到根这条链的贡献，可以扫描线上李超线段树维护转移。
第二个是直接树剖，树剖成 \(O(\log n)\) 个前缀和 \(1\) 个区间，区间用线段树套李超线段树，前缀扫一遍李超线段树就行。
第三个用出栈序作为线段树套李超线段树的下标，发现对于目前这个点，只有祖先没有出栈，也就是说访问过的点中，只有祖先在该点出栈序之后，并且能够发现祖先是按顺序排的，也就是说可以直接用 目前的点的出栈序 到 目标祖先的出栈序 这个区间进行转移。
CF1746F Kazaee
挺离谱的。随机映射 \(t\) 次 \(x\to d_x\)，其中 \(d\) 是随机的一个序列，每次检验区间和是否是 \(k\) 的倍数。可以理解为每次均匀分布，所以出错概率是 \(\frac{1}{k^t}\)，取 \(t=30\) 大概一定能过了。但是如果你写的不是二分离散化那有可能被卡哈希表需要卡常。
P4899 [IOI2018] werewolf 狼人
某个点分树博客应该会用到这个题的做法。
建立两棵 Kruskal 重构树（因为是点权所以把点权拍到边权上，注意取 \(\min\) 或 \(\max\)），一个最小，一个最大。找到最大树中 \(S_i\) 可到的所有 \(\geq L\) 的点和最小树中 \(E_i\) 可到的所有 \(\leq R\) 的点，显然这是两棵子树。只需要这两棵子树 \(\leq n\) 的点集部分有交即可。在第一棵树上 dsu，然后第二棵树 BIT 维护子树和即可。
标签：子树,祖先,线段,李超,栈序,哈希,杂题 From： https://www.cnblogs.com/xingyuxuan/p/18646457