ABC267F 题解
DaiRuiChen007
2022-11-24 17:35:22
# ABC267F 题解
## 思路分析
考虑对于每个点 $u$ 选择一个距离 $u$ 最远的节点 $p$，然后将 $p$ 作为根节点，求出 $u$ 的 $k$ 级祖先即可。
注意到对于 $1\sim n$ 的每个节点，这样的 $p$ 只可能是某个直径的两个端点，因此求出直径端点 dfs 即可。
求 $k$ 级祖先的时候不用倍增，直接在树上记录上一个深度为 $x$ 的点 $d_x$，由于 dfs 序的特征，对于某个点 $u$ 其 $k$ 级祖先就是 $d_{dep_u-k}$。
时间复杂度 $\Theta(n+q)$。
## 代码呈现
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
vector <int> edge[MAXN],query[MAXN];
int ans[MAXN],node[MAXN],dis[MAXN],len;
inline void dfs(int p,int f,int dep) {
node[dep]=p;
for(int q:query[p]) if(dep>=dis[q]) ans[q]=node[dep-dis[q]];
len=max(len,dep);
for(int v:edge[p]) if(v!=f) dfs(v,p,dep+1);
}
signed main() {
int n,q;
scanf("%d",&n);
for(int i=1;i<n;++i) {
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
scanf("%d",&q);
for(int i=1;i<=q;++i) {
int u;
scanf("%d%d",&u,&dis[i]);
query[u].push_back(i);
}
for(int turn:{0,1,2}) {
int pos=node[len]; len=0;
if(!turn) pos=1;
dfs(pos,0,0);
}
for(int i=1;i<=q;++i) printf("%d\n",ans[i]?ans[i]:-1);
return 0;
}
```