洛谷P3379 【模板】最近公共祖先(LCA)(树链剖…
2018-06-17 21:27:00来源:未知 阅读 ()
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式:
第一行包含三个正整数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。
树链剖分求LCA
不断跳,跳到一条重链
输出在上面的
不用写线段树
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=2*1e6+10; #define ls k<<1 #define rs k<<1|1 inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++; } inline int read() { char c=nc();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();} while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();} return x*f; } struct node { int u,v,nxt; }edge[MAXN]; int head[MAXN]; int num=1; void AddEdge(int x,int y) { edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++; } int fa[MAXN],deep[MAXN],tot[MAXN],son[MAXN],top[MAXN],cnt; int dfs1(int now,int f,int dep) { deep[now]=dep; fa[now]=f; tot[now]=1; int maxson=-1; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v==f) continue; tot[now]+=dfs1(edge[i].v,now,dep+1); if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v; } return tot[now]; } void dfs2(int now,int topf) { top[now]=topf; if(!son[now]) return ; dfs2(son[now],topf); for(int i=head[now];i!=-1;i=edge[i].nxt) if(edge[i].v!=son[now]&&edge[i].v!=fa[now]) dfs2(edge[i].v,edge[i].v); } int LCA(int x,int y) { while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); return x; } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); int N=read(),M=read(),root=read(); for(int i=1;i<=N-1;i++) { int x=read(),y=read(); AddEdge(x,y);AddEdge(y,x); } dfs1(root,0,1); dfs2(root,root); while(M--) { int x=read(),y=read(); printf("%d\n",LCA(x,y)); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:HTTP下载图片
下一篇:洛谷P3384 【模板】树链剖分
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
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