ABC267F 题解

· · 题解

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)。

代码呈现

#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;
}