3083: 遥远的国度

唔,没初始化 wa了一次…
思路很一眼。
就是说 考虑 树剖
如果 查询点是首都的祖先,那么查询点构成的子树就是 整个树除了 查询点包含 首都的儿子以外所有点。
那么 知道一个子树在树剖上是连续一段区间, 即 现在需要求 出 包含首都的那棵子树的根,
用类似倍增lca的方法即可。
对于查询点不是首都的祖先的情况,答案直接为 查询点这棵子树 的答案
搞定
c++代码如下:

 

8 + 7 =