Ancestor Inquiry#
Description#
Given a rooted tree. There are m inquiries. Each inquiry provides a pair of nodes x and y, and outputs the ancestral relationship between x and y.
Input#
The first line contains the number of nodes n. The next n lines each contain a pair of integers a and b, indicating that there is an edge between a and b. If b == -1, then a is the root of the tree. The next line contains an integer m, indicating the number of inquiries. The following m lines each contain two positive integers x and y.
Output#
For each inquiry, if x is the ancestor of y, output 1; if y is the ancestor of x, output 2; otherwise, output 0.
Input Example 1#
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
Output Example 1#
1
0
0
0
2
Hint#
For 30% of the data, n and m <= 1000. For 100% of the data, n and m <= 40000, and the number of each node does not exceed 40000.
Idea#
Jump up the deeper node until they are at the same depth. If they are the same node, then one is the ancestor of the other.
Okay, I probably understand what doubling is.
The first time I wrote the tree into a structure.
Note that in the two input nodes, the second one is the father.
Code#
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e4+5,H=16;
struct tree{
public:
void clear(void){
memset(e,0,sizeof(ed));
memset(head,0,sizeof(head));
memset(depth,0,sizeof(depth));
memset(f,0,sizeof(f));
newp=0;
bfsed=0;
}
void vAdd(int p1,int p2){
++newp;
e[newp].to=p2;
e[newp].nex=head[p1];
e[newp].frm=p1;
fa[p2]=p1;
head[p1]=newp;
}
void setSize(int s){
size=s;
h=(log(size)/log(2)+0.5);
}
int getSize(void){
return size;
}
void setRoot(int r){
root_node=r;
}
int root(void){
return root_node;
}
int getDepth(int node){
if(!bfsed){
bfs_for_depth();
}
return depth[node];
}
bool checkFa(int son,int fat){
for(int i=h;i>=0;--i){
if(depth[f[son][i]]>=depth[fat]){
son=f[son][i];
}
}
if(son==fat)return 1;
else return 0;
}
private:
struct ed{
int to,nex,frm;
} e[MAXN];
int head[MAXN],newp,size,root_node,depth[MAXN],fa[MAXN],f[MAXN][H];
bool bfsed;
int h;
void bfs_for_depth(void){
queue<int> q;
depth[root_node]=1;
q.push(root_node);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].nex){
int y=e[i].to;
depth[y]=depth[x]+1;
f[y][0]=x;
for(int j=1;j<=h;++j){
f[y][j]=f[f[y][j-1]][j-1];
}
q.push(y);
}
}
bfsed=1;
}
};
tree a;
int main(void){
a.clear();
int n,m;
scanf("%d",&n);
a.setSize(n);
for(int i=1;i<=n;++i){
int p1,p2;
scanf("%d%d",&p1,&p2);
if(p2==-1){
a.setRoot(p1);
}
else {
a.vAdd(p2,p1);
}
}
scanf("%d",&m);
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
if(x!=y&&a.getDepth(x)==a.getDepth(y)){
printf("0\n");
}
else{
int ans=0;
int dp1=a.getDepth(x);
int dp2=a.getDepth(y);
if(dp1>dp2){
if(a.checkFa(x,y)){
ans=2;
}
}
else{
if(a.checkFa(y,x)){
ans=1;
}
}
printf("%d\n",ans);
}
}
return 0;
}