祖孙询问
(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.