Trick——树

Part1

问题：统计一条根链上的点权值出现次数。

首先不难想到对根链建立主席树，可以做到 \(O(nlogn)-O(logn)\) 的优秀复杂度。
码量有些大，但它是在线算法。

离线算法
我们这样考虑：
若知道 \(x\) 的根链的点权集合，那么可以 \(O(1)\) 转移为 \(fa_x\) 和 \(son_x\) 的根链点权集合。（本质上是莫队的思想）
于是通过离线将询问放在点上，通过一次 \(dfs\) 统计答案，点权集合用 桶 或 哈希表。
时间复杂度 \(O(n)\)。
另一种思考角度：可以理解为搜索时的路径记录。

拓展问题：树上任意两点之间的链上的点权值出现次数。
这可以通过树上前缀和进行转化为根链问题。（\(ans_{x,y}=ans_{x,1}+ans_{y,1}-ans_{lca,1}-ans_{fa_{lca},1}\)）