树剖+线段树77pts 3wa

rt

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
struct TREE{
    int l,r,val,tag;
}tree[401010];
vector<int> v[101010];
int n,T,used[101010],root[101010],dep[101010],fa[101010],siz[101010],heav[101010],tot;
void dfs(int fat,int p,int depth)
{
    dep[p] = depth,fa[p] = fat,siz[p]++;
    int i;
    for(i = 0;i < v[p].size();i++)
    {
        int k = v[p][i];
        if(k == fat)continue;
        dfs(p,k,depth + 1);
        siz[p] += siz[k];
        if(siz[heav[p]] < siz[k])heav[p] = k;
    }
}
void bdrt(int fat,int p,int rt)
{
    used[p] = ++tot,root[p] = rt;
    if(heav[p])bdrt(p,heav[p],rt);
    int i;
    for(i = 0;i < v[p].size();i++)
    {
        int k = v[p][i];
        if(k == fat || k == heav[p])continue;
        bdrt(p,k,k);
    }
}
void pushdown(int s)
{
    tree[s << 1].val += (tree[s << 1].r - tree[s << 1].l + 1) * tree[s].tag;
    tree[s << 1 | 1].val += (tree[s << 1 | 1].r - tree[s << 1 | 1].l + 1) * tree[s].tag;
    tree[s << 1].tag += tree[s].tag;
    tree[s << 1 | 1].tag += tree[s].tag;
    tree[s].tag = 0;
}
void build(int s,int l,int r)
{
    tree[s].l = l,tree[s].r = r;
    tree[s].tag = tree[s].val = 0;
    if(l == r)return;
    int mid = l + r >> 1;
    build(s << 1,l,mid);
    build(s << 1 | 1,mid + 1,r);
}
void modify(int s,int l,int r)
{
    if(tree[s].l == l && tree[s].r == r)
    {
        tree[s].val += tree[s].r - tree[s].l + 1;
        tree[s].tag++;
        return;
    }
    if(tree[s].tag)pushdown(s);
    int mid = tree[s].l + tree[s].r >> 1;
    if(l > mid)modify(s << 1 | 1,l,r);
    else if(r <= mid)modify(s << 1,l,r);
    else modify(s << 1,l,mid),modify(s << 1 | 1,mid + 1,r);
    tree[s].val = tree[s << 1].val + tree[s << 1 | 1].val;
}
void Tmodify(int x1,int x2)
{
    while(root[x1] != root[x2])
        if(dep[root[x1]] < dep[root[x2]]) modify(1,used[root[x2]],used[x2]),x2 = fa[root[x2]];
        else modify(1,used[root[x1]],used[x1]),x1 = fa[root[x1]];
    if(dep[x1] < dep[x2]) modify(1,used[x1] + 1,used[x2]);
    else modify(1,used[x2] + 1 * (x1 != x2),used[x1]);
}
int query(int s,int x)
{
    if(tree[s].r < x || tree[s].l > x)return 0;
    if(tree[s].l == tree[s].r)return tree[s].val;
    if(tree[s].tag)pushdown(s);
    return query(s << 1,x) + query(s << 1 | 1,x);
}
int main()
{
    cin>>n>>T;
    int i,j;
    for(i = 1;i < n;i++)
    {
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    build(1,1,n);
    dfs(0,1,1);
    bdrt(0,1,1);
    while(T--)
    {
        char op;cin>>op;
        if(op == 'P')
        {
            int l,r;cin>>l>>r;
            Tmodify(l,r);
        }
        else
        {
            int l,r;cin>>l>>r;
            cout<<query(1,fa[l] == r ? used[l] : used[r])<<endl;
        }
    }
}