求调教

求调教 70分代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,fa[N][(int)log2(N)],dep[N],x,y;
vector<int>edge[N];
void dfs(int u,int pre){
  dep[u]=dep[pre]+1;
  fa[u][0]=pre;
  for(int i=1;i<=(int)log2(n);i++){
  	fa[u][i]=fa[fa[u][i-1]][i-1];
  }
  for(int v:edge[u]){
  	if(v==pre)continue;
  	dfs(v,u);
  }
}
int lca(int u,int v){
  if(dep[u]<dep[v])swap(u,v);
  for(int i=(int)log2(n);i>=0;i--){
  	if(dep[u]-(1<<i)>=dep[v]){
  		u=fa[u][i];
  	}
  }
  if(u==v)return u;
  for(int i=(int)log2(n);i>=0;i--){
  	if(fa[u][i]==fa[v][i])continue;
  	u=fa[u][i],v=fa[v][i];
  }
  return fa[u][0];
}
int main(){
  cin>>n>>m>>s;
  for(int i=1;i<=n-1;i++){
  	cin>>x>>y;
  	edge[x].push_back(y);
  	edge[y].push_back(x);
  }
  dfs(s,0);
  for(int i=1;i<=m;i++){
  	cin>>x>>y;
  	cout<<lca(x,y)<<endl;
  }
}