- 关于树上的路径 \(a_1 \to a_2 \to a_3 \to a_4 \to ... \to a_n\) （\(a_i\) 与 \(a_{i+1}\) 之间未必有边，路径可重复）的路径并处理问题
如果我们面临多次询问，每次给你一堆点，然后让你把这一堆点形成的路径并处理好，加到统计数组里面。即，最后我们查询的是，每个点被多少个路径覆盖。
我们利用这样一个 trick：把点按照 dfn 排序，依次考虑。
排序后，我们发现，对于 \(\forall i \in [1,n]\) ，进行覆盖操作： \(a_i \to a_{i+1}\)。定义 \(a_{n+1} = a_1\)。这样每个点刚好被加两遍。
遇到类似问题，也可以试着考虑相邻的东西想一想。说不定能胡出惊喜。
- 关于树上路径 \(x \to a_i\) 的覆盖问题
同样和上面，多组数据最后求累加答案，怎么做？
同样我们考虑按照 dfn 排序。对于相邻的两个点，重合部分在 LCA 及其上方。
具体的，我们考虑树上差分，对于所有点，\(d_{a_i}\) 加一；对于相邻的 LCA，\(d_{\text{LCA}}\) 减一。
如果需要在线询问单点的覆盖情况，可以 BIT 维护 dfn 序形成的序列。
例题：P5480 with ACam
标签：10,路径,覆盖,树论,Trick,dfn,LCA,排序 From： https://www.cnblogs.com/BreakPlus/p/17062304.html