祖孫詢問#
描述#
已知一顆有根樹。有 m 個詢問。每個詢問給出了一對節點 x,y, 輸出 x,y 的祖孫關係
輸入#
第一行節點數目 n 接下來 n 行，每行一對整數 a,b, 表示 a 和 b 之間有邊。如果 b==-1，那麼 a 就是數根接下來是一個整數 m，表示詢問的個數接下來 m 行，每行兩個正整數 x,y
輸出#
對於每一個詢問，如果 x 是 y 的祖先，輸出 1；如果 y 是 x 的祖先，輸出 2；否則輸出 0
輸入範例 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
輸出範例 1#
1
0
0
0
2
提示#
對於 30% 的數據，n,m<=1000 對於 100% 的數據，n,m<=40000, 每個節點的編號都不超過 40000
思路#
將深的那個節點一直往上跳，跳到同一深度後如果是同一個節點那一個就是另一個的祖先。
好吧大概搞懂什麼是倍增了。
第一次把樹寫到結構體裡面。
注意輸入的兩個節點中，後面那個是爸爸。
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;
}