给一个家谱，回答给的操作结果。
1）L 按照字典序排序儿子，输出整个家谱。
2）b 求出所给name的所有兄弟。
3）c 求出两个name的LCA
读入数据时，我用一个curfather数组维护固定深度的爸爸，之后就可以方便的将所给的数据形式转换成邻接表建图，同时使用map存储name和id号。Tree结构体数组存储每个人的信息，父亲，儿子（vector存储，方便排序等操作），name，深度。
L操作将每个人的儿子排序，递归打印。
b操作直接找到他父亲，用size函数计算儿子数。
c操作用st表+DFS在线求解。
这道题还有两个坑，根的兄弟要输出1，a和b的lca是a或b时，所求为其lca的父亲。
还有就是递归打印会暴栈，要交C++用黑科技的扩栈语句。
//这个题用了我好久，先学LCA，再纠结怎么处理输入数据，立下不a出来不吃饭的flag，最终a了。。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#pragma comment(linker,"/STACK:102400000,102400000") using namespace std; const int maxn = ;
int N,M,T,rmq[*maxn]; struct ST
{
int stTable[*maxn][];
int prelog2[*maxn]; void init(int n)
{
prelog2[] = ;stTable[][] = ;
for(int i=;i <= n;i++)
{
prelog2[i] = prelog2[i-];
stTable[i][] = i;
if(( << (prelog2[i]+)) == i) ++prelog2[i];
}
for(int i=n;i > ;i--)
{
for(int j=;(i+(<<j)-) < n;j++)
{
stTable[i][j] = rmq[stTable[i][j-]] < rmq[stTable[i+(<<(j-))][j-]] ? stTable[i][j-] : stTable[i+(<<(j-))][j-];
}
}
} int query(int a,int b)
{
if(a > b) swap(a,b);
int k = prelog2[b-a+];
return rmq[stTable[a][k]] < rmq[stTable[b-(<<k)+][k]] ? stTable[a][k] : stTable[b-(<<k)+][k];
}
}; struct Node
{
int to,next;
}; struct LCA
{
int n;
Node edge[*maxn];
int tol,head[maxn],Dfs[*maxn],P[maxn],cnt;
bool vis[maxn];
ST st; void init(int n)
{
this->n = n;
tol = ;
memset(head,-,sizeof head);
} void add_edge(int a,int b)
{
edge[tol].to = b;
edge[tol].next = head[a];
head[a] = tol++;
edge[tol].to = a;
edge[tol].next = head[b];
head[b] = tol++;
} int query(int a,int b)
{
//printf("%d %d:%d\n",P[a],P[b],st.query(P[a],P[b]));
return Dfs[st.query(P[a],P[b])];
} void dfs(int a,int deepth)
{
vis[a] = true;
++cnt;
Dfs[cnt] = a;
rmq[cnt] = deepth;
P[a] = cnt;
//printf("cnt=%d\n",cnt);
for(int i = head[a];i != -;i = edge[i].next)
{
int v = edge[i].to;
if(vis[v]) continue;
dfs(v,deepth+);
++cnt;
Dfs[cnt] = a;
rmq[cnt] = deepth;
}
} void solve(int root)
{
memset(vis,false,sizeof vis);
cnt = ;
//printf("root=%d\n",root);
dfs(root,);
st.init(*n-);
} }lca; int num = ;
int curfather[maxn];
struct Node_son
{
int deepth;
int fa;
vector<int> son;
string name;
}Tree[maxn]; bool cmpson(const int a,const int b) { return Tree[a].name < Tree[b].name;} void Print_Tree(int root)
{
for(int i=;i<Tree[root].deepth;i++) cout << '.';
cout << Tree[root].name << endl;
if(Tree[root].son.empty()) return;
sort(Tree[root].son.begin(),Tree[root].son.end(),cmpson); for(int i=;i < (int)Tree[root].son.size();i++)
{
Print_Tree(Tree[root].son[i]);
}
} int main()
{
while(cin>>N && N)
{
lca.init(N);
map <string ,int > m;
memset(curfather,,sizeof curfather); for(int i=;i<N;i++)
{
cin>>Tree[i].name;
Tree[i].son.clear();
int lev = ;
for(int t = ;t < (int)Tree[i].name.size();t++)
{
if(Tree[i].name[t] != '.') break;
else lev++;
}
Tree[i].name.erase(Tree[i].name.begin(),Tree[i].name.begin()+lev);
m.insert(pair<string,int>(Tree[i].name,i));
Tree[i].deepth = lev; curfather[lev+] = i;
if(lev == ) continue;
Tree[i].fa = curfather[lev];
Tree[Tree[i].fa].son.push_back(i);
lca.add_edge(Tree[i].fa+,i+);
}
string op;cin >> T;
lca.solve(); while(T--)
{
cin >> op;
if(op[] == 'L') //重构树，字典序
{
Print_Tree();
}
else if(op[] == 'b') //兄弟数
{
string son;
cin >> son;
if(son == Tree[].name) cout << <<endl;
else cout << Tree[ Tree[m[son]].fa ].son.size()<<endl;
}
else if(op[] == 'c') //LCA DFS+ST
{
string son1,son2;
cin >> son1 >> son2;
int lllca = lca.query(m[son1]+,m[son2]+) - ;
if(lllca == m[son1] || lllca == m[son2])
cout << Tree[Tree[lllca].fa].name << endl;
else cout << Tree[ lca.query(m[son1]+,m[son2]+) - ].name<<endl;
}
}
}
}