使用了倍增的LCA，有时间再去学Tarjan
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstring> using namespace std; const int maxn=10010; const int maxm=60; int t,i,j,k,tot=0,n,m; struct seg{int x,next;}v[maxn]; int dp[maxn][maxm],d[maxn],base[maxn],f[maxn]; int add(int x,int y) { v[++tot].x=y; v[tot].next=base[x]; base[x]=tot; } int dfs(int x) { for (int i=1;i<=k;i++) dp[x][i]=dp[dp[x][i-1]][i-1]; for (int i=base[x];i;i=v[i].next) d[v[i].x]=d[x]+1,dfs(v[i].x); } int swap(int &x,int &y) { int tmp=y; y=x; x=tmp;} int lca(int x,int y) { if (d[x]<d[y]) swap(x,y); for (int i=k;i>=0;i--) if (d[dp[x][i]]>=d[y]) x=dp[x][i]; if (x==y) return x; for (int i=k;i>=0;i--) if (dp[x][i]!=dp[y][i]) x=dp[x][i],y=dp[y][i]; return dp[x][0]; } int main() { //freopen("1.in","r",stdin); scanf("%d",&t); while (t--) { scanf("%d",&n); tot=0; k=30; memset(v,0,sizeof(v)); memset(base,0,sizeof(base)); memset(dp,0,sizeof(dp)); memset(f,0,sizeof(f)); memset(d,0,sizeof(d)); int x,y; for (int i=1;i<=n-1;i++) {scanf("%d%d",&x,&y);add(x,y);f[y]=x;dp[y][0]=x;} for (int i=1;i<=n;i++) if (f[i]==0) ,d[i]=1,dfs(i); scanf("%d%d",&x,&y); printf("%d ",lca(x,y));} }