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

输入格式 第一行包含三个正整数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。

做这个题之前，刚学了树链剖分，这就用上了，求最近公共祖先（LCA）其实就是用树链剖分后，进行简单的链查询即可（让那两个结点的指针中所处链的顶端结点深度小的（也就是靠下的那条链）的指针不断向上跳啊，跳啊。。。直到两指针在同一条链时返回深度较小的那个指针所指的结点编号（即为LCA）即可）。

完整代码：

#include #include #include #include #define int long long using namespace std; const int maxn=5e5+5; typedef struct Edge { int next,to; }edg; edg e[maxn<<1]; int n,m,s,cnt,head[maxn<<1];

void AddEdge(int u,int v) { e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt++; }

int fa[maxn],son[maxn],depth[maxn],siz[maxn]; void dfs1(int u,int f) { fa[u]=f; depth[u]=depth[f]+1; siz[u]=1; int maxsize=-1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>maxsize) { maxsize=siz[v]; son[u]=v; } } }

int tim,dfn[maxn],top[maxn]; void dfs2(int u,int t) { dfn[u]=++tim; top[u]=t; if(!son[u]) return; dfs2(son[u],t); for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(vfa[u]||vson[u]) continue; dfs2(v,v); } }

int query(int x,int y) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); x=fa[top[x]]; } if(depth[x]>depth[y]) swap(x,y); return x; }

signed main() { // ios::sync_with_stdio(false); // cin.tie(0); memset(head,-1,sizeof(head)); scanf("%lld%lld%lld",&n,&m,&s); int N=n-1; while(N--) { int u,v; scanf("%lld%lld",&u,&v); AddEdge(u,v); AddEdge(v,u); } dfs1(s,s); dfs2(s,s); while(m--) { int x,y; scanf("%lld%lld",&x,&y); int ans=query(x,y); cout<<ans<<endl; } }