PKU Campus 2011 B A Problem about Tree lca倍增

本文主要是介绍PKU Campus 2011 B A Problem about Tree lca倍增，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B:A Problem about Tree

总时间限制: 

1000ms 

内存限制: 

65536kB

描述

Given a tree with Nvertices and N- 1 edges, you are to answer Qqueries on "which vertex isY's parent if we choose Xas the root of the entire tree?". 　

输入

The first line of input is an integer T, the number of test cases.
The first line of each test case contains N(2 ≤ N ≤ 10000) and Q(1 ≤ Q ≤ 10000).
Each of the following N - 1 lines of the test case contains two integers a(1 ≤ a ≤ N) and b(1 ≤b ≤ N) indicating an edge between a and b.
Each of the following Q lines of the test case contains two integers X(1 ≤ X ≤ N) and Y(1 ≤ Y≤ N, Y ≠ X) indicating an query.
　

输出

For each query, output the Y's parent if X is the root of tree.

样例输入

1
5 3
1 2
1 3
4 3
3 5
2 3
4 1
5 2

样例输出

1
3
1

题意：n个节点的一棵树，m次询问：求以x为根y的父亲节点。

思路：lca倍增算法。利用bfs求出每个节点的深度以及2^i倍祖先。接下来求x和y的lca,如果lca!=y,那么y的父节点就是ancestor[y][0],不然求x的depth[x]-depth[y]-1祖先结点。画图还是比较看粗来的，详见程序：

#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=10000+100;
int n,m,edge_cnt;
int head[MAXN],ancestor[MAXN][15],depth[MAXN];
struct Edge
{int v;int next;
}edge[2*MAXN];
void init()
{edge_cnt=0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{edge[edge_cnt].v=v;edge[edge_cnt].next=head[u];head[u]=edge_cnt++;
}
void bfs(int root)
{queue<int>Q;ancestor[root][0]=root; depth[root]=0;Q.push(root);while(!Q.empty()){int u=Q.front(); Q.pop();for(int i=1;i<15;i++)ancestor[u][i]=ancestor[ancestor[u][i-1]][i-1];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==ancestor[u][0])continue;depth[v]=depth[u]+1; ancestor[v][0]=u;Q.push(v);}}
}
int lca(int x,int y)
{if(depth[x]<depth[y]) swap(x,y);for(int i=0;i<15;i++)if((depth[x]-depth[y])&(1<<i)) x=ancestor[x][i];if(x==y)return x;for(int i=14;i>=0;i--)if(ancestor[x][i]!=ancestor[y][i])x=ancestor[x][i],y=ancestor[y][i];return ancestor[x][0];
}
int main()
{//freopen("text.txt","r",stdin);int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);init();for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v); addedge(v,u);}bfs(1);while(m--){int x,y;scanf("%d%d",&x,&y);int fa=lca(x,y);if(fa==y){int D=depth[x]-depth[y]-1;while(D){int k=(int)(log10(1.0*D)/log10(2.0));x=ancestor[x][k];D-=(1<<k);}printf("%d\n",x);}elseprintf("%d\n",ancestor[y][0]);}}return 0;
}

这篇关于PKU Campus 2011 B A Problem about Tree lca倍增的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---