来源：POJ1330
使用dfs序来寻找子树的信息，随后就可以完成这个答案了
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; const int MAXN = 10000+10; int n; vector<int>tree[MAXN]; bool vis[MAXN]; int in[MAXN],dep[MAXN<<1],has[MAXN<<1]; int dp[MAXN<<1][20]; int id; void dfs(int rt,int depth){ dep[++id] = depth; has[id] = rt; if(!in[rt]) in[rt] = id; int nxt; for(int i=0;i<tree[rt].size();i++){ nxt = tree[rt][i]; dfs(nxt,depth+1); has[++id] = rt; dep[id] = depth; } return ; } void stpre(){ //cout<<"id = "<<id<<endl; for(int i=1;i<=id;i++) dp[i][0] = i; for(int l=1;(1<<l)<=id;l++){ for(int i=1;i<=id;i++){ if(i+(1<<l)-1<=id){ int xx = dp[i][l-1]; int yy = dp[i+(1<<(l-1))][l-1]; if(dep[xx]>dep[yy]) dp[i][l] = yy; else dp[i][l] = xx; } } } } int query(int l,int r){ int k=(int)(log(double(r-l+1))/log(2.0)); int xx = dp[l][k]; int yy = dp[r-(1<<k)+1][k]; //cout<<"id: "<<xx<<" "<<yy<<endl; if(dep[xx]>dep[yy]) return has[yy]; else return has[xx]; } int main(){ int T; int x,y; scanf("%d",&T); while(T--){ memset(vis,false,sizeof(vis)); scanf("%d",&n); for(int i=1;i<=n;i++) tree[i].clear(); for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); tree[x].push_back(y); vis[y] = true; } int root = -1; for(int i=1;i<=n;i++){ if(!vis[i]){ root = i; break; } } id = 0; memset(dep,0,sizeof(dep)); memset(in,0,sizeof(in)); memset(has,0,sizeof(has)); memset(dp,0,sizeof(dp)); dfs(root,1); //cout<<"---------"<<endl; //for(int i=1;i<=id;i++){ // cout<<i<<" "<<has[i]<<" "<<dep[i]<<endl; //} //cout<<"----------"<<endl; //cout<<"2*n-1 = "<<2*n-1<<" id = "<<id<<endl; //for(int i=1;i<=n;i++) cout<<i<<" "<<in[i]<<endl; stpre(); scanf("%d%d",&x,&y); if(in[x]>in[y]) cout<<query(in[y],in[x])<<endl; else cout<<query(in[x],in[y])<<endl; } return 0; }