Accepted/20568K/5956MS

bzoj1103.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=250005;
int a[maxn],b[maxn];
int bit[maxn*3];
int seq[maxn*3],tot;
bool vis[maxn];
int fa[maxn];
int n,m;
int tu,tv;
vector <int> e[maxn];
typedef vector<int>::iterator ii;
void dfs(int u)
{
    a[u]=++tot;
    seq[tot]=u;
    for (ii i=e[u].begin();i!=e[u].end();i++)
        if (!a[*i])
            dfs(*i);
    b[u]=++tot;
    seq[tot]=-u;
}
int lowbit(int u)
{
    return u&(-u);
}
void edit(int u,int d)
{
    for (;u<=tot;u+=lowbit(u))
        bit[u]+=d;
}
int sum(int u)
{
    int r=0;
    for (;u>0;u-=lowbit(u))
        r+=bit[u];
    return r;
}
int main()
{
    char op[5];
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        scanf("%d%d",&tu,&tv);
        e[tu].push_back(tv);
        e[tv].push_back(tu);
    }
    dfs(1);
    for (int i=1;i<=n;i++)
    {
        edit(a[i],1);
        edit(b[i],-1);
    }
    scanf("%d",&m);
    m+=n-1;
    while (m--)
    {
        scanf("%s",op);
        if (op[0]=='W')
        {
            scanf("%d",&tu);
            printf("%d\n",sum(a[tu])-1);
        }else
        {
            scanf("%d%d",&tv,&tu);
            if (a[tv]<a[tu])
                swap(tu,tv);
            edit(a[tv],-1);
            edit(b[tv],1);
        }
    }
    return 0;
}