就是把分治思想搬到树上去了。
- 例题 给你一个树，边有边权，问你是否存在长度为 \(k\) 的一条简单路径。\(0.2s,n\leq 10^4,Q\leq 100,k\leq 10^7\) 。
板题。我们令 \(rt\) 表示根节点，容易发现只有两种点会对答案造成贡献。
- 经过 \(rt\) 的，在子树内部完成的。我们先计算经过 \(rt\) 的，然后换根到儿子继续算即可。
问题转化为如何找到一条经过 \(rt\) 的路径。我们用 \(v_i\) 表示 \(rt\) 的第 \(i\) 棵子树，先遍历一遍，然后求出 \(∀x \in v_i ,dis(rt,x)\) 。然后直接枚举，然后看 \(Judge[Q_i-dis(rt,x)]\) 是否存在即可。 \(Judge\) 是一个类似桶的东西，用来记录 \(v_1 \text{~}v_{i-1}\) 的到节点的距离。
注意点：
- \(rt\) 找重心。
- 遍历完子树后，\(Judge\) 记得清空！
- \(Judge\) 是一个类似桶的东西，最好开大点，不然容易 \(GG\) 。实在不行可以 \(Hash\) 。