思路：利用flag来标记儿子结点，最后只有根节点没有被标记，那么没有被标记的点也就是根节点被我们找到了
在线做法：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> using namespace std; const int maxn=10000+10; const int M=20; struct node { int v,next; }e[maxn]; int bit[M]; int dp[maxn<<1][M],depth[maxn<<1],euler[maxn<<1],pos[maxn],head[maxn],vis[maxn],flag[maxn]; int T,n,tot; void Swap(int &a,int &b) { int c; c=a; a=b; b=c; } void build(int u,int v) { e[T].v=v; e[T].next=head[u]; head[u]=T++; } void init() { memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); memset(flag,0,sizeof(flag)); T=0; tot=0; int u,v; for(int i=0;i<n-1;i++) { scanf("%d%d",&u,&v); build(u,v); flag[v]=1; } } void dfs(int u,int dep) { vis[u]=1; euler[++tot]=u; depth[tot]=dep; pos[u]=tot; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(!vis[v]) { dfs(v,dep+1); euler[++tot]=u; depth[tot]=dep; } } } void ST(int len) { for(int i=1;i<=len;i++) dp[i][0]=i; int k=(int )(log(len*1.0)/log(2.0)); for(int j=1;j<=k;j++) { for(int i=1;i+bit[j]<=len;i++) { int l=dp[i][j-1]; int r=dp[i+bit[j-1]][j-1]; dp[i][j]=depth[l]<depth[r]?l:r; } } } int RMQ(int x,int y) { int len=y-x+1; int k=(int )(log(len*1.0)/log(2.0)); int l=dp[x][k]; int r=dp[y-bit[k]+1][k]; return depth[l]<depth[r]?l:r; } void lca(int x,int y) { int l=pos[x]; int r=pos[y]; if(l>r) Swap(l,r); printf("%d ",euler[RMQ(l,r)]); return; } int main() { //freopen("in.txt","r",stdin); for(int i=0;i<M;i++) bit[i]=1<<i; int kase; scanf("%d",&kase); while(kase--) { scanf("%d",&n); init(); for(int i=1;i<=n;i++) { if(!flag[i]) { dfs(i,1); break; } } ST(2*n-1); int ql,qr; scanf("%d%d",&ql,&qr); lca(ql,qr); } return 0; }
离线做法：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <vector> using namespace std; const int maxn=10000+10; struct node { int v,next; }e[maxn<<1]; int head[maxn],vis[maxn],fa[maxn],flag[maxn]; int T,n; int ql,qr,q; void build(int u,int v) { e[T].v=v; e[T].next=head[u]; head[u]=T++; } void init() { memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) fa[i]=i; memset(flag,0,sizeof(flag)); T=0; q=0; int u,v; for(int i=0;i<n-1;i++) { scanf("%d%d",&u,&v); build(u,v); flag[v]=1; //build(v,u); } scanf("%d%d",&ql,&qr); } int getf(int x) { while(x!=fa[x]) { fa[x]=getf(fa[x]); x=fa[x]; } return x; } void dfs(int u) { vis[u]=1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(!vis[v]) { dfs(v); fa[v]=u; } } if(q==1) return; if(u==qr&&vis[ql]) { q=1; printf("%d ",getf(ql)); return ; } if(u==ql&&vis[qr]) { q=1; printf("%d ",getf(qr)); return ; } } int main() { //freopen("in.txt","r",stdin); int kase; scanf("%d",&kase); while(kase--) { scanf("%d",&n); init(); for(int i=1;i<=n;i++) { if(!flag[i]) { dfs(i); break; } } } return 0; }
第一行在线ac的，第二行是离线ac的，从时间和空间复杂度来看离线做法更加优越