LCA树剖法模板

P3379 【模板】最近公共祖先（LCA）

题目描述

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

时空限制：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。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct data{
 7     int next,to;
 8 }edge[1000010];
 9 struct dt{
10     int fa,son,size,deep,top,num,end;
11 }tree[500010];
12 int head[500010];
13 int n,m,r,cnt,tot;
14 void add_edge(int start,int end){
15     edge[++cnt].next=head[start];
16     edge[cnt].to=end;
17     head[start]=cnt;
18 }
19 void dfs_weight(int u){
20     tree[u].size=1;
21     tree[u].son=0;
22     for(int i=head[u];i;i=edge[i].next)
23         if(edge[i].to!=tree[u].fa){
24             tree[edge[i].to].fa=u;
25             tree[edge[i].to].deep=tree[u].deep+1;
26             dfs_weight(edge[i].to);
27             tree[u].size+=tree[edge[i].to].size;
28             if(tree[edge[i].to].size>tree[tree[u].son].size) tree[u].son=edge[i].to;
29         }
30     return;
31 }
32 void dfs_build(int u,int tp){
33     tree[u].top=tp;
34     tree[u].num=++tot;
35     if(tree[u].son){
36         dfs_build(tree[u].son,tp);
37         for(int i=head[u];i;i=edge[i].next)
38             if(edge[i].to!=tree[u].fa&&edge[i].to!=tree[u].son) dfs_build(edge[i].to,edge[i].to);
39     }
40     tree[u].end=tot;
41     return;
42 }
43 int lca(int aa,int bb){
44     int f1=tree[aa].top,f2=tree[bb].top;
45     while(f1!=f2){
46         if(tree[f1].deep>tree[f2].deep){
47             aa=tree[f1].fa;
48             f1=tree[aa].top;
49         }
50         else{
51             bb=tree[f2].fa;
52             f2=tree[bb].top;
53         }
54     }
55     if(tree[aa].deep<tree[bb].deep) return aa;
56     else return bb;
57 }
58 int main(){
59     scanf("%d%d%d",&n,&m,&r);
60     int uu,vv;
61     for(int i=1;i<n;i++){
62         scanf("%d%d",&uu,&vv);
63         add_edge(uu,vv);
64         add_edge(vv,uu);
65     }
66     dfs_weight(r);
67     dfs_build(r,r);
68     for(int i=1;i<=m;i++){
69         scanf("%d%d",&uu,&vv);
70         printf("%d
",lca(uu,vv));
71     }
72     return 0;
73 }