题目描述

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

输入格式

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

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

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

输出格式

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

AC代码（树剖）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int head[1000001],to[1000001],next[1000001],cnt;
 5 int n,m,s,x,y,maxn;
 6 int fa[1000001],top[1000001],dep[1000001],siz[1000001],zs[1000001];
 7 
 8 void add(int u,int v)
 9 {
10     cnt++;
11     next[cnt]=head[u];
12     head[u]=cnt;
13     to[cnt]=v;
14 }
15 
16 int init(int k,int f,int d)
17 {
18     fa[k]=f;
19     dep[k]=d;
20     siz[k]=1;
21     maxn=-1;
22     for (int i=head[k];i;i=next[i])
23     {
24         if (to[i]!=f)
25         {
26             siz[k]+=init(to[i],k,d+1);
27             if (siz[to[i]]>maxn)
28             {
29                 maxn=siz[to[i]];
30                 zs[k]=to[i];
31             }
32         }
33     }
34     return siz[k];
35 }
36 
37 void dfs(int k,int Top)
38 {
39     top[k]=Top;
40     if (zs[k]==0)
41         return ;
42     dfs(zs[k],Top);
43     for (int i=head[k];i;i=next[i])
44     {
45         if (top[to[i]]==0)
46             dfs(to[i],to[i]);
47     }
48 }
49 
50 int query(int x,int y)
51 {
52     while (top[x]!=top[y])
53     {
54         if (dep[top[x]]<dep[top[y]])
55             swap(x,y);
56         x=fa[top[x]];
57     }
58     if (dep[x]<dep[y])
59         return x;
60     else
61         return y;
62 }
63 
64 int main()
65 {
66     scanf("%d%d%d",&n,&m,&s);
67     for (int i=1;i<n;i++)
68     {
69         scanf("%d%d",&x,&y);
70         add(x,y); add(y,x);
71     }
72     init(s,0,1);
73     dfs(s,s);
74     while (m--)
75     {
76         scanf("%d%d",&x,&y);
77         printf("%d\n",query(x,y));
78     }
79     return 0;
80 }