POJ上的题，其实就是LCA板子。先预处理每个点倍增祖先，然后每组询问先使x和y达到同一深度，然后一起往上跳到公共祖先的+1深度的点。
die码：
#include<cstdio> #include<algorithm> #define maxn 500010 using namespace std; int head[maxn],nxt[maxn<<1],to[maxn<<1],cnt; int deep[maxn],f[maxn][21]; inline void add(int x,int y) { nxt[++cnt]=head[x]; head[x]=cnt; to[cnt]=y; } inline void dfs(int id,int fa) { deep[id]=deep[fa]+1; f[id][0]=fa; for(int i=1;i<=20;i++) f[id][i]=f[f[id][i-1]][i-1]; for(int i=head[id];i;i=nxt[i]) { if(to[i]==fa) continue; dfs(to[i],id); } } inline int lca(int x,int y) { if(deep[x]<deep[y]) swap(x,y); for(int i=20;i>=0;i--) if(deep[f[x][i]]>=deep[y]) x=f[x][i]; if(x==y) return y; for(int i=20;i>=0;i--) { if(f[x][i]==f[y][i]) continue; x=f[x][i],y=f[y][i]; } return f[x][0]; } int main() { int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1,a,b;i<n;i++) { scanf("%d%d",&a,&b); add(a,b),add(b,a); } dfs(s,0); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); printf("%d\n",lca(x,y)); } return 0; }
转载于:https://www.cnblogs.com/charlesss/p/10579850.html
相关资源：25个经典网站源代码