祖孫の質問#
説明#
根付き木が与えられます。m 個の質問があります。それぞれの質問では、ノード x と y のペアが与えられ、x と y の祖孫関係を出力します。
入力#
最初の行にノードの数 n が与えられます。以下の n 行には、各行に整数 a と b のペアが与えられます。a と b の間に辺がある場合、b が - 1 の場合、a は木の根です。その後に整数 m が与えられ、続く m 行には、それぞれの質問に対して 2 つの正の整数 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 を超えません。
アプローチ#
深い方のノードを上にジャンプし続け、同じ深さに到達したら、同じノードであれば、一方は他方の祖先です。
倍増が何を意味するのか、大体理解しました。
最初に木を構造体に書き込むことにしましょう。
入力の 2 つのノードのうち、後ろのノードが親です。
コード#
#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;
}