- 关于树上的路径 \(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