传送门：http://poj.org/problem?id=1330
题意：很裸的最近公共祖先，看题就知道…模板题。
代码：
/* *********************************************** Author :Torrance_ZHANG Created Time :2016/4/29 22:11:34 File Name :ceshi2.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> typedef long long int LL; using namespace std; const int MAXN=10010; int qx,qy,res; struct Edge{ int to; int next; Edge(){ to=-1; next=-1; } }edge[MAXN]; int deg[MAXN]; //统计入度，找根 int n,cnt,head[MAXN],fa[MAXN],rnk[MAXN],vis[MAXN]; //rnk统计节点的秩，即深度 void add(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; cnt++; } int Find(int x){ return x==fa[x]?fa[x]:fa[x]=Find(fa[x]); } void Tarjan(int x){ fa[x]=x; for(int i=head[x];i!=-1;i=edge[i].next){ Tarjan(edge[i].to); fa[edge[i].to]=x; } if(x==qx||x==qy){ if(x!=qx) swap(qx,qy); if(fa[qy]) res=Find(fa[qy]); } } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t; scanf("%d",&t); while(t--){ cnt=0; res=0; memset(head,-1,sizeof(head)); memset(deg,0,sizeof(deg)); memset(fa,0,sizeof(fa)); scanf("%d",&n); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); deg[y]++; } int root=0; scanf("%d%d",&qx,&qy); for(int i=1;i<=n;i++){ if(deg[i]==0){ root=i; break; } } Tarjan(root); printf("%d ",res); } return 0; }
在线算法：邝斌模板
/* *********************************************** Author :Torrance_ZHANG Created Time :2016/5/3 22:22:56 File Name :ceshi.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> typedef long long int LL; using namespace std; const int MAXN=10010; struct Edge{ int to,next; }edge[MAXN<<1]; int rmq[MAXN<<1]; //depth struct ST{ int mm[MAXN<<1]; int dp[MAXN<<1][20]; void init(int n){ mm[0]=-1; for(int i=1;i<=n;i++){ mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; dp[i][0]=i; } for(int j=1;j<=mm[n];j++) for(int i=1;i+(1<<j)-1<=n;i++) dp[i][j]=rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1]; } int query(int a,int b){ if(a>b) swap(a,b); int k=mm[b-a+1]; return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?dp[a][k]:dp[b-(1<<k)+1][k]; } }; int tot,cnt; int val[MAXN<<1]; int first[MAXN]; int head[MAXN]; ST st; void init(){ tot=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } void dfs(int u,int pre,int dep){ val[++cnt]=u; rmq[cnt]=dep; first[u]=cnt; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==pre) continue; dfs(v,u,dep+1); val[++cnt]=u; rmq[cnt]=dep; } } void init_LCA(int root,int node_num){ cnt=0; dfs(root,root,0); st.init(node_num*2-1); } int query_lca(int u,int v){ return val[st.query(first[u],first[v])]; } int deg[MAXN]; int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); init(); memset(deg,0,sizeof(deg)); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); deg[y]++; } int root; for(int i=1;i<=n;i++){ if(deg[i]==0){ root=i; break; } } init_LCA(root,n); /*for(int i=1;i<=n;i++) cout<<rmq[i]<<" "; puts(""); for(int i=1;i<=n;i++) cout<<val[i]<<" "; puts(""); for(int i=1;i<=n;i++) cout<<first[i]<<" "; puts("");*/ int qx,qy; scanf("%d%d",&qx,&qy); printf("%d ",query_lca(qx,qy)); } return 0; }