PJOI PKU Campus 2011 B:A Problem about Tree LCA 求随意点x为根的y的父节点

题目链接：点击打开链接

题意:给定n个点 m个询问

以下n-1行给定一棵树

m个询问 x y

问把树转成以x为根 y的父节点是谁

第一种情况lca==y那就是x的第 dep[x] - dep[y] -1 父亲，依次向上爬山坡，利用倍增的二进制加速。

另外一种就是Father[y];

#include"cstdio"
#include"iostream"
#include"queue"
#include"algorithm"
#include"set"
#include"queue"
#include"cmath"
#include"string.h"
#include"vector"
using namespace std;
#define N 10050
#define e 2.718281828459
struct Edge{
int from, to, dis, nex;
}edge[5*N];
int head[N],edgenum,dis[N],fa[N][20],dep[N];
void add(int u,int v,int w){
Edge E={u,v,w,head[u]};
edge[edgenum] = E;
head[u]=edgenum++;
}
void bfs(int root){
queue<int> q;
fa[root][0]=root;dep[root]=0;dis[root]=0;
q.push(root);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u]; ~i;i=edge[i].nex){
int v=edge[i].to;if(v==fa[u][0])continue;
dep[v]=dep[u]+1;dis[v]=dis[u]+edge[i].dis;fa[v][0]=u;
q.push(v);
}
}
}
int Lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void init(){memset(head, -1, sizeof head); edgenum = 0;}
int n, m;
int main(){
int T, i, j, x, y;scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
init();
for(i=1;i<n;i++){scanf("%d %d",&x,&y);add(x,y,1);add(y,x,1);}
bfs(1);
while(m--){
scanf("%d %d",&x,&y);
int lca = Lca(x,y);
if(lca==y){
int D = dep[x] - dep[y]-1;
while(D){
int z = (int)(log10(1.0*D)/log10(2.0));
x = fa[x][z];
D-=1<<z;
}
printf("%d\n",x);
}
else printf("%d\n",fa[y][0]);
}
}
return 0;
}