P3379 【模板】最近公共祖先(LCA)
2018-06-17 22:38:51来源:未知 阅读 ()
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式:第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。
接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。
输出格式:输出包含M行,每行包含一个正整数,依次为每一个询问的结果。
输入输出样例
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash