祖孙询问

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1129 字

已知一棵有根树，多次询问x、y的祖孙关系：x

一本通
练习

正文

/*
原题：T1557 「一本通 4.4 练习 2」祖孙询问
题意：已知一棵有根树，多次询问 x、y 的祖孙关系：x 是 y 祖先输出 1，y 是 x 祖先输出 2，否则 0。
思路：从根 DFS 求每个点的入/出时间戳 in、out；x 是 y 祖先当且仅当 in[x]<=in[y] 且 out[y]<=out[x]。
复杂度：O(n+m)。
易错点：节点编号不连续，数组要按最大编号开；用 in/out 区间判定而不是简单深度比较。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=40005;
int n,m;
vector<vector<int>> g;
vector<int> in,out;
int tim=0;
void dfs(int u,int p){
    in[u]=++tim;
    for(int v:g[u]){
        if(v==p) continue;
        dfs(v,u);
    }
    out[u]=tim;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    g.assign(N,vector<int>());
    int root=1;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        if(b==-1) root=a;
        else{
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }
    in.assign(N,0);
    out.assign(N,0);
    dfs(root,0);
    cin>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        bool xAnc=(in[x]<=in[y]&&out[y]<=out[x]);
        bool yAnc=(in[y]<=in[x]&&out[x]<=out[y]);
        if(xAnc) cout<<1<<'\n';
        else if(yAnc) cout<<2<<'\n';
        else cout<<0<<'\n';
    }
    return 0;
}

祖孙询问

正文

一本通·提高篇的其它内容