LCA 模板 JZOJ 3054. 【NOIP2012模拟10.27】祖孙询问


//luo
 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 using namespace std;
 5 int n,root,m;
 6 vector <int> f[1000100];
 7 int depth[1000100];
 8 int fa[10000100];
 9 inline int read()
10 {
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 void dfs(int fath,int now)
17 {
18     depth[now]=depth[fath]+1;
19     fa[now]=fath;
20     for (int i=0;i<f[now].size();i++)
21         dfs(now,f[now][i]);
22 }
23 int LCA(int x,int y)
24 {
25     if (depth[y]>depth[x])
26         swap(x,y);
27     while (depth[x]>depth[y])
28        x=fa[x];
29     while (x!=y)
30       x=fa[x],y=fa[y];
31     return x;
32 }
33 int main ()
34 {
35     
36     cin>>n;
37     for (int i=1,x,y;i<=n;i++)
38     {
39         x=read(); y=read();
40         if (y==-1)
41           root=x;
42         f[y].push_back(x);
43     }
44     depth[0]=-1;
45     dfs(0,root);
46     cin>>m;
47     for (int i=1,x,y;i<=m;i++)
48     {
49         x=read(); y=read();
50         int s=LCA(x,y);
51         if (s==x) cout<<1<<endl;
52         else if (s==y) cout<<2<<endl;
53         else
54            cout<<0<<endl;
55     }
56 }

倍增优化

我们每次可以不仅仅局限于一步一步的跳

原来加上记录他跳几次的点就好了

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 using namespace std;
 5 int n,root,m;
 6 vector <int> f[100010];
 7 int depth[100010];
 8 int fa[1000010][22];
 9 inline int read()
10 {
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 void dfs(int fath,int now)
17 {
18     depth[now]=depth[fath]+1;
19     fa[now][0]=fath;
20     for (int i=1;i<21;i++)
21        fa[now][i]=fa[fa[now][i-1]][i-1];
22     for (int i=0;i<f[now].size();i++)
23         dfs(now,f[now][i]);
24 }
25 int LCA(int x,int y)
26 {
27     if (depth[y]>depth[x])
28         swap(x,y);
29     for (int i=20;i>=0;i--)
30        if (depth[x]-(1<<i)>=depth[y])
31          x=fa[x][i];
32     if (x==y) return x;
33     for (int i=20;i>=0;i--)
34        if (fa[x][i]!=fa[y][i])
35          x=fa[x][i],y=fa[y][i];
36     return fa[x][0];
37 }
38 int main ()
39 {
40     
41     cin>>n;
42     for (int i=1,x,y;i<=n;i++)
43     {
44         x=read(); y=read();
45         if (y==-1)
46           root=x;
47         f[y].push_back(x);
48     }
49     depth[0]=-1;
50     dfs(0,root);
51     cin>>m;
52     for (int i=1,x,y;i<=m;i++)
53     {
54         x=read(); y=read();
55         int s=LCA(x,y);
56         if (s==x) cout<<1<<endl;
57         else if (s==y) cout<<2<<endl;
58         else
59            cout<<0<<endl;
60     }
61 }

Description

已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。

Input

输入第一行包括一个整数n表示节点个数。

接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。

第n+2行是一个整数m表示询问个数。

接下来m行，每行两个正整数x和y。

Output

对于每一个询问，输出1:如果x是y的祖先，输出2:如果y是x的祖先，否则输出0。

Sample Input

Sample Output

Data Constraint

Hint

对于100%的.据,n,m≤40000，每个节点的编号都不超过40000。

为何要逼自己长大，去闯不该闯的荒唐