思路：就是个比较裸的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][],ans[Maxn][];
vector<int> head[Maxn];
map< string,int> g;
void init()
{
Md=;
memset(pre,,sizeof(pre));
memset(vi,,sizeof(vi));
memset(dep,,sizeof(dep));
memset(farther,,sizeof(farther));
memset(sec,,sizeof(sec));
for(int i=;i<=;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=;i<sz;i++)
{
now=head[u][i];
dep[now]=dep[u]+;
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]=;
}
else
{
if(dep[u]%Md==)
sec[u]=farther[u];
else
sec[u]=sec[farther[u]];
}
sz=head[u].size();
for(i=;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])<;
}
void dfssort(int u)
{
int i,v,sz;
sz=head[u].size();
sort(head[u].begin(),head[u].end(),cmp);
for(i=;i<sz;i++)
{
dfssort(head[u][i]);
}
}
void Out(int u)
{
int i,v,sz;
printf("%s\n",str[u]);
sz=head[u].size();
for(i=;i<sz;i++)
{
v=head[u][i];
Out(v);
}
}
int main()
{
int n,i,j,cnt,q;
char cc[];
while(scanf("%d",&n)!=EOF,n)
{
init();
scanf("%s",str[]);
strcpy(ans[],str[]);
g[str[]]=;
pre[]=;
for(i=;i<n;i++)
{
scanf("%s",str[i]);
j=;
cnt=;
while(str[i][j]=='.')
{
cnt++;
j++;
}
int pos=;
while(str[i][j]!='\0')
{
cc[pos++]=str[i][j];
j++;
}
cc[pos]='\0';
g[cc]=i;
strcpy(ans[i],cc);
add(pre[cnt-],i);
pre[cnt]=i;
}
dfssort();
dfs();
Md=sqrt(1.0*Md);
make_sec();
scanf("%d",&q);
for(i=;i<=q;i++)
{
scanf("%s",cc);
if(cc[]=='L')
{
Out();
}
else
if(cc[]=='b')
{
scanf("%s",cc);
int v=g[cc];
printf("%d\n",head[farther[v]].size());
}
else
if(cc[]=='c')
{
char s1[],s2[];
scanf("%s%s",s1,s2);
int u=g[s1];
int v=g[s2];
int ff=LCA(u,v);
if(ff==u)
{
printf("%s\n",ans[farther[u]]);
}
else
if(ff==v)
{
printf("%s\n",ans[farther[v]]);
}
else
printf("%s\n",ans[ff]);
}
}
}
return ;
}