学步园

题意：按照题目描述给一棵树（家族谱，节点n<=30000），有m（m<=30000）次操作，L代表字典序最小的dfs序列，b name 输出name的brother有多少个，

          c name name输出两个人的lca是多少（lca不能是name本身）。

题解：vector存储节点数这样很容易排序，然后保存下L的序列，sum[ i ]表示当前 i 节点的直接儿子节点的个数，rmq处理出lca。

Sure原创，转载请注明出处。

#pragma comment (linker , "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>
#include <string>
#include <cmath>
using namespace std;
const int maxn = 30002;
vector <int> vv[maxn];
map <string , int> hash;
string name[maxn],str;
int up[maxn],dep[maxn],biao[maxn],sum[maxn],fa[maxn];
int E[maxn << 1],D[maxn << 1],bj[maxn],dp[maxn << 1][17];
int m,n,top,tot,bound;

bool cmp(int a,int b)
{
    return name[a] < name[b];
}

void init()
{
    memset(up,-1,sizeof(up));
    memset(sum,0,sizeof(sum));
    memset(fa,-1,sizeof(fa));
    hash.clear();
    for(int i=0;i<n;i++)
    {
        vv[i].clear();
    }
    return;
}

void read()
{
    getchar();
    cin>>name[0];
    up[0] = 0;
    for(int i=1;i<n;i++)
    {
        cin>>str;
        int j = 0,len = str.length();
        while(str[j] == '.') j++;
        up[j] = i;
        vv[up[j-1]].push_back(i);
        name[i] = str.substr(j);
        hash[name[i]] = i;
    }
    return;
}

void dfs(int st,int h)
{
    dep[st] = h;
    biao[tot++] = st;
    E[++top] = st;
    D[top] = h;
    bj[st] = top;
    for(int i=0;i<vv[st].size();i++)
    {
        fa[vv[st][i]] = st;
        sum[st]++;
        dfs(vv[st][i] , h+1);
        E[++top] = st;
        D[top] = h;
    }
    return;
}

void init_rmq()
{
    for(int i=1;i<=top;i++)
    {
        dp[i][0] = i;
    }
    for(int j=1;j<=bound;j++)
    {
        for(int i=1;i + (1 << j) - 1 <= top;i++)
        {
            if(D[dp[i][j-1]] < D[dp[i + (1 << (j-1))][j-1]])
            {
                dp[i][j] = dp[i][j-1];
            }
            else
            {
                dp[i][j] = dp[i + (1 << (j-1))][j-1];
            }
        }
    }
    return;
}

int askrmq(int l,int r)
{
    if(l > r) swap(l , r);
    int d = log((double)(r - l + 1)) / log(2.0);
    int wei = -1;
    if(D[dp[l][d]] < D[dp[r - (1 << d) + 1][d]])
    {
        wei = dp[l][d];
    }
    else
    {
        wei = dp[r - (1 << d) + 1][d];
    }
    return E[wei];
}

void make()
{
    for(int i=0;i<n;i++)
    {
        sort(vv[i].begin() , vv[i].end() , cmp);
    }
    top = tot = 0;
    dfs(0,0);
    bound = log((double)(top + 1)) / log(2.0);
    init_rmq();
    return;
}

void out()
{
    for(int i=0;i<tot;i++)
    {
        for(int j=0;j<dep[biao[i]];j++) printf(".");

        cout<<name[biao[i]]<<endl;
    }
    return;
}

void solve()
{
    scanf("%d",&m);
    getchar();
    char cc[3];
    while(m--)
    {
        scanf("%s",cc);
        if(cc[0] == 'L') out();
        else if(cc[0] == 'b')
        {
            cin>>str;
            int pos = hash[str];
            if(pos == 0) puts("1");
            else printf("%d\n",sum[fa[pos]]);
        }
        else
        {
            cin>>str;
            int x = hash[str];
            cin>>str;
            int y = hash[str];
            int lca = askrmq(bj[x] , bj[y]);
            if(lca == x) lca = fa[lca];
            if(lca == y) lca = fa[lca];
            cout<<name[lca]<<endl;
        }
    }
    return;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        init();
        read();
        make();
        solve();
    }
    return 0;
}