首先,非常显然的一点是,\(a,b,c\) 在一条到根的链上。
然后我们可以分别讨论 \(a\) 和 \(b\) 的祖孙关系。
首先记 \(size_p\) 表示以 \(p\) 为根的子树大小,\(dep_p\) 表示 \(p\) 的深度。
那么同一条链上 \(a,b\) 的距离就是 \(|dep_a - dep_b|\)。
先考虑 \(b\) 是 \(a\) 的祖先的情况,那么 \(c\) 有 \(size_a - 1\) 种可能(除去 \(a\) 本身),\(b\) 有 \(\min(dep_a - 1,x)\) 种可能(避免距离超出 \(x\) 或超出根)。
乘起来就好了。
再考虑 \(a\) 是 \(b\) 的祖先的情况,这个时候就比较麻烦了。
假如已知 \(b\),\(c\) 的可能性有 \(size_b - 1\) 种。
然鹅现在我们要考虑 \(b\) 的选择要满足的条件: 1. \(b\) 在 \(a\) 的子树内。 2. \(dep_b \in (dep_a,dep_a + x]\)。
对于第二个条件,我们可以用权值线段树来维护。
对于第一个条件,我们可以线段树合并。
然后在线的话,需要把线段树合并的过程可持久化一下。
代码:
1 |
|