P3379 【模板】最近公共祖先(LCA)

2018-06-17 22:38:51来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

输入输出格式

输入格式:

第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。

接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。

输出格式:

输出包含M行,每行包含一个正整数,依次为每一个询问的结果。

输入输出样例

输入样例#1:
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出样例#1:
4
4
1
4
4

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=10000,M<=10000

对于100%的数据:N<=500000,M<=500000

样例说明:

该树结构如下:

第一次询问:2、4的最近公共祖先,故为4。

第二次询问:3、2的最近公共祖先,故为4。

第三次询问:3、5的最近公共祖先,故为1。

第四次询问:1、2的最近公共祖先,故为4。

第五次询问:4、5的最近公共祖先,故为4。

故输出依次为4、4、1、4、4。

 

很多人说这道题不能用倍增写

其实是可以的,只不过需要加一点读入优化罢了

注意倍增的最大值一定要取19而不能取20,因为这题卡常!!

代码比较简单,没有用位运算,也写了大量的注释并标明了易错点,大家可以参考一下

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=1000001;
 7 int n,m,root;
 8 struct node
 9 {
10     int u;
11     int v;
12     int next;
13 }edge[MAXN];
14 int num=1;
15 int head[MAXN];
16 int deep[MAXN];
17 int f[MAXN][20];
18 void edge_add(int x,int y)
19 {
20     edge[num].u=x;
21     edge[num].v=y;
22     edge[num].next=head[x];
23     head[x]=num++;
24 }
25 void build_tree(int p)
26 {
27     for(int i=head[p];i!=-1;i=edge[i].next)// 遍历与p节点相邻的节点 
28     {
29         int will=edge[i].v;
30         if(deep[will]==0)// 如果点will没有被访问过的话 
31         {
32             deep[will]=deep[p]+1;// 则点will的深度==p的深度+1 
33             f[will][0]=p;// will点向上跳2^0的节点是p 
34             build_tree(will);//继续初始化will节点 
35         }
36     }
37 }
38 void initialize_step()
39 {
40     for(int i=1;i<=19;i++)
41         for(int j=1;j<=n;j++)
42             f[j][i]=f[f[j][i-1]][i-1];
43     // 第j个节点,向上跳i能到达的节点就是 跳到i-1处再向上跳i-1能到达的节点
44     // 因为倍增是以次方的形式增加的 
45 }
46 int LCA(int x,int y)
47 {
48     if(deep[x]<deep[y])swap(x,y);// 如果说节点x的深度比节点y的深度小的话,就交换他俩的位置,让x<y 
49     for(int i=19;i>=0;i--)// 因为跳的步数越小越好,所以从最大的值开始跳
50     {
51         if(deep[f[x][i]]>=deep[y])// 如果跳完i步之后x还在y下方的话 ,这里必须加等于号 
52         x=f[x][i];// 就更新x的值,继续跳
53     }
54     if(x==y)return y;//判断一下,如果x和y在同一条线上,就直接返回x的值 ,y也可以 
55     
56     for(int i=19;i>=0;i--)//再让x和y一起向上跳
57     if(f[x][i]!=f[y][i])
58     x=f[x][i],y=f[y][i];// 如果他们跳完之后的祖先不相等的话,就继续跳 
59     return f[x][0];//按这样跳下去,一定会跳到只要再跳一步就能找到最近公共祖先的位置! 
60 }
61 void read(int & x)
62 {
63     char c=getchar();x=0;
64     while(c<'0'||c>'9')c=getchar();
65     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();// 读入优化,必须要有! 
66 }
67 int main()
68 {
69     //scanf("%d%d%d",&n,&m,&root);
70     read(n);read(m);read(root);
71     for(int i=1;i<=n;i++)head[i]=-1;
72     for(int i=1;i<=n-1;i++)
73     {
74         int x,y;
75         //scanf("%d%d",&x,&y);
76         read(x);read(y);
77         edge_add(x,y);
78         edge_add(y,x);
79     }
80     deep[root]=1;//将根节点的深度设为1 
81     build_tree(root);// 建立起一棵树 
82     initialize_step();// 初始化向上跳的距离 
83     for(int i=1;i<=m;i++)
84     {
85         int x,y;
86         //scanf("%d%d",&x,&y);
87         read(x);read(y);// 求x与y的最近公共祖先
88         printf("%d\n",LCA(x,y));// ans 
89     }
90     return 0;
91 } 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU1754 I HATE IT

下一篇:P2320 [HNOI2006]鬼谷子的钱袋