下面掌声有请你谷众复读机开始复读
by x义x @ 2019-01-12 11:55:01
希望更丰富的展现？使用Markdown
by 33028120040712wcl @ 2019-01-12 11:58:21
希望更丰富的展现？使用Markdown
by jc2018 @ 2019-01-12 12:00:51
```cpp
include<bits/stdc++.h>
using namespace std; int n,m,s,cnt,f,t; int fa[500005][19]; int head[500005]; int dp[500005]; bool v[500005]; struct bian { int to; int nxt; }a[1000005]; void add(int u,int v) { cnt++; a[cnt].to=v; a[cnt].nxt=head[u]; head[u]=v; } void dfs(int x) { v[x]=true; for(int i=head[x];i;i=a[i].nxt) { int u=a[i].to; if(v[u]) continue; else { fa[u][0]=x; dp[u]=dp[x]+1; dfs(u); } } } int lca(int f,int t) { if(dp[f]<dp[t]) swap(f,t); int mx; for(mx=0;(1<<mx)<=dp[f];mx++); mx--; for(int i=mx;i>=0;i--) { if(dp[f]-(1<<i)>=dp[t]) f=fa[f][i]; } if(f==t) return f; for(int i=mx;i>=0;i--) { if(fa[f][i]!=fa[t][i]&&fa[f][i]!=0) { f=fa[f][i]; t=fa[t][i]; } } return fa[f][0]; } int main() { cin>>n>>m>>s; for(int i=1;i<=n-1;i++) { int u,v; cin>>u>>v; add(u,v); add(v,u); } dp[s]=1; fa[s][0]=s; dfs(s); for(int j=0;(1<<j)<=n;j++) for(int i=1;i<=n;i++) if(fa[i][j-1]) fa[i][j]=fa[fa[i][j-1]][j-1]; for(int i=1;i<=m;i++) { cin>>f>>t; cout<<lca(f,t)<<endl; } return 0; }
```
by jc2018 @ 2019-01-12 12:01:17
希望更丰富的展现？使用Markdown
by Mr_Wu @ 2019-01-12 12:01:42
```
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
const int MAXN = 500500;
const int INF = 0x3f3f3f3f;
using namespace std;
struct graph{//前向星
struct node{
int next=0,to,w;
}edge[MAXN*2];int edge_long=0,head[MAXN];
int n,m,root,dep[MAXN];
int fa[MAXN][21];
void build(int x,int y,int v){
edge_long++;
edge[edge_long].w=v;
edge[edge_long].next=head[x];
edge[edge_long].to=y;
head[x]=edge_long;
}
void LCA_first(int u,int father){
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=0;i<=19;i++)
fa[u][i+1]=fa[fa[u][i]][i];
for(int i=head[u];i;i=edge[i].next){
if(edge[i].to!=father){
LCA_first(edge[i].to,u);
}
}
}
int LCA(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
for(int i=20;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]){
x=fa[x][i];
}
if(x==y)return x;
}
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
}tree;
int main()
{
int x,y;
scanf("%d%d%d",&tree.n,&tree.m,&tree.root);
for(int i=1;i<tree.n;i++){
scanf("%d%d",&x,&y);
tree.build(x,y,1);tree.build(y,x,1);
}
tree.LCA_first(tree.root,0);
for(int i=1;i<=tree.m;i++){
scanf("%d%d",&x,&y);
printf("%d\n",tree.LCA(x,y));
}
}
```
by Freddie @ 2019-01-23 09:42:35