祖孙询问
(tree.pas/c/cpp)
【问题描述】
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y,询问x与y的祖孙关系。
【输入格式】
输入第一行包括一个整数n表示节点个数。
接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1,那么a就是树的根。
第n+2行是一个整数m表示询问个数。
接下来m行,每行两个正整数x和y。
【输出格式】
对于每一个询问,输出1:如果x是y的祖先,输出2:如果y是x的祖先,否则输出0。
【样例输入】
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234233
23312
23313
23315
23319
【样例输出】
1
0
0
0
2
【数据规模】
对于30%的数据,n,m≤1000。
对于100%的.据,n,m≤40000,每个节点的编号都不超过40000。
先看看标准方法求LCA(msm法):
为了处理爆栈而进行各种压缩变量,卡内存过关(边表记得*2)
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<cctype> #include<functional> #include<algorithm> #include<iostream> using namespace std; #define MAXN (80000+10) /* #define f( i , j ) f[ ( i ) + 2 , j ] #define b( i ) b [ ( i ) + 2 ] */ int n,m,f[MAXN][100],len[MAXN],deep[MAXN]; int head[MAXN],next[MAXN],edge[MAXN],siz=0; int log2(int x) { return (int)trunc(log(x)/log(2)); } void addedge(int u,int v) { edge[++siz]=v; next[siz]=head[u]; head[u]=siz; } int a[MAXN]={0},tot=0; bool b[MAXN]; void dfs(int x,int dep) { /* cout<<x<<':'; for (int i=1;i<=tot;i++) cout<<a[i]<<' '; cout<<endl; */ b[x]=1; int p=head[x]; while (p) { int now=edge[p]; tot++; a[tot]=now; if (!b[now]) dfs(now,dep+1); tot--; p=next[p]; } /* cout<<x<<':'; for (int i=1;i<=tot;i++) cout<<a[i]<<' '; cout<<endl; */ int j=0; for (int i=tot-1;i>=1;i-=(tot-i)) { f[x][j]=a[i]; j++; } len[x]=j-1; deep[x]=dep; } int father(int x,int y) { while (y) { int p=log2(y); x=f[x][p]; y-=(1<<p); } return x; } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); memset(head,0,sizeof(head)); memset(next,0,sizeof(next)); memset(edge,0,sizeof(edge)); memset(len,0,sizeof(len)); memset(b,0,sizeof(b)); memset(deep,0,sizeof(deep)); scanf("%d",&n); for (int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x+2,y+2);addedge(y+2,x+2); } a[1]=1;tot=1; dfs(1,0); /* for (int i=1;i<=n+2;i++) { cout<<i<<' '<<len[i]<<':'; for (int j=0;j<=len[i];j++) cout<<f[i][j]<<' '; cout<<endl; } */ scanf("%d",&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); x+=2;y+=2; // cout<<x<<' '<<y<<' '<<deep[x]<<' '<<deep[y]<<endl; if (x==1) printf("1n"); else if (y==1) printf("2n"); else { int depx=deep[x],depy=deep[y]; if (depx<depy) { if (father(y,depy-depx)==x) printf("1n"); else printf("0n"); } else if (depx>depy) { if (father(x,depx-depy)==y) printf("2n"); else printf("0n"); } else printf("0n"); } } // while (1); return 0; }
考虑欧拉路径——它可以判断2个节点的从属情况
模拟栈版本:巧用while循环代替dfs
Program tree; const maxn=40000; maxm=40000; var n,m,i,j,u,v,size,x,y:longint; head,next,edge:array[-1..maxm*2] of longint; // dfs stack:array[1..maxm*10] of longint; b:array[-1..maxn] of boolean; l,r,father:array[-1..maxn] of longint; time,nowstack:longint; Procedure addedge(u,v:longint); begin inc(size); edge[size]:=v; next[size]:=head[u]; head[u]:=size; end; Procedure dfs; var i,j,p,now,v:longint; flag:boolean; begin time:=0;nowstack:=1; stack[1]:=-1; while (nowstack>0) do begin flag:=false; now:=stack[nowstack]; inc(time); if not(b[now]) then begin b[now]:=true;l[now]:=time; end; p:=head[now]; while (p>0) do begin if not(b[edge[p]]) then begin v:=edge[p]; father[v]:=now; inc(nowstack); stack[nowstack]:=v; flag:=true;break; end; p:=next[p]; end; if flag then continue; inc(time); r[now]:=time; dec(nowstack); end; end; begin assign(input,'tree.in'); assign(output,'tree.out'); reset(input); rewrite(output); read(n); fillchar(head,sizeof(head),0); fillchar(l,sizeof(l),0); fillchar(r,sizeof(r),0); fillchar(b,sizeof(b),false); size:=0; for i:=1 to n do begin read(u,v); addedge(u,v); addedge(v,u); end; dfs; read(m); for i:=1 to m do begin read(x,y); if (l[x]<l[y]) and (r[y]<r[x]) then writeln('1') else if (l[y]<l[x]) and (r[x]<r[y]) then writeln('2') else writeln('0'); end; close(input); close(output); end.