思路：就是个比较裸的LCA了，不过要注意的是，如果a和b的公共祖先是a，那么答案就是farther[a]。
#include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<map> #include<string> #include<iostream> #include<cstdio> #define Maxn 300010 using namespace std; int vi[Maxn],pre[Maxn]; int dep[Maxn],sec[Maxn],farther[Maxn]; int e,Md; char str[Maxn][70],ans[Maxn][70]; vector<int> head[Maxn]; map< string,int> g; void init() { Md=0; memset(pre,0,sizeof(pre)); memset(vi,0,sizeof(vi)); memset(dep,0,sizeof(dep)); memset(farther,0,sizeof(farther)); memset(sec,0,sizeof(sec)); for(int i=0;i<=300000;i++) head[i].clear(); g.clear(); } void add(int u,int v) { head[u].push_back(v); } void dfs(int u) { int i,j,now,sz; sz=head[u].size(); for(i=0;i<sz;i++) { now=head[u][i]; dep[now]=dep[u]+1; farther[now]=u; dfs(now); } Md=max(Md,dep[u]); } void make_sec(int u) { int i,j,now,sz; if(dep[u]<Md) { sec[u]=0; } else { if(dep[u]%Md==0) sec[u]=farther[u]; else sec[u]=sec[farther[u]]; } sz=head[u].size(); for(i=0;i<sz;i++) { now=head[u][i]; make_sec(now); } } int LCA(int a,int b) { int x=a,y=b; while(sec[a]!=sec[b]) { if(dep[a]>dep[b]) a=sec[a]; else b=sec[b]; } while(a!=b) { if(dep[a]>dep[b]) a=farther[a]; else b=farther[b]; } return a; } int cmp(int a,int b) { return strcmp(ans[a],ans[b])<0; } void dfssort(int u) { int i,v,sz; sz=head[u].size(); sort(head[u].begin(),head[u].end(),cmp); for(i=0;i<sz;i++) { dfssort(head[u][i]); } } void Out(int u) { int i,v,sz; printf("%s ",str[u]); sz=head[u].size(); for(i=0;i<sz;i++) { v=head[u][i]; Out(v); } } int main() { int n,i,j,cnt,q; char cc[70]; while(scanf("%d",&n)!=EOF,n) { init(); scanf("%s",str[0]); strcpy(ans[0],str[0]); g[str[0]]=0; pre[0]=0; for(i=1;i<n;i++) { scanf("%s",str[i]); j=0; cnt=0; while(str[i][j]=='.') { cnt++; j++; } int pos=0; while(str[i][j]!=' ') { cc[pos++]=str[i][j]; j++; } cc[pos]=' '; g[cc]=i; strcpy(ans[i],cc); add(pre[cnt-1],i); pre[cnt]=i; } dfssort(0); dfs(0); Md=sqrt(1.0*Md); make_sec(0); scanf("%d",&q); for(i=1;i<=q;i++) { scanf("%s",cc); if(cc[0]=='L') { Out(0); } else if(cc[0]=='b') { scanf("%s",cc); int v=g[cc]; printf("%d ",head[farther[v]].size()); } else if(cc[0]=='c') { char s1[70],s2[70]; scanf("%s%s",s1,s2); int u=g[s1]; int v=g[s2]; int ff=LCA(u,v); if(ff==u) { printf("%s ",ans[farther[u]]); } else if(ff==v) { printf("%s ",ans[farther[v]]); } else printf("%s ",ans[ff]); } } } return 0; }