萌新刚学OI，求调树剖，37pts其他全部RE

rt，虽然树剖这种恶心东西可能没人调，不过我翻遍提交记录发现没有一个37pts的/dk

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> g[N];
int f[N],dep[N],siz[N],mxson[N];
int dfn[N],top[N];
void dfs1(int x,int fa){
    f[x]=fa;
    dep[x]=dep[fa]+1;
    siz[x]=1;
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==fa)continue;
        dfs1(to,x);
        siz[x]+=siz[to];
        if(siz[mxson[x]]<siz[to])mxson[x]=to;
    }
}
int cnt;
void dfs2(int x,int topf){
    top[x]=topf;
    dfn[x]=++cnt;
    if(!mxson[x])return;
    dfs2(mxson[x],topf);
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==f[x]||to==mxson[x])continue;
        dfs2(to,to);
    }
}
struct tree{
    int l,r,tag;
}t[N*4];
void build(int l,int r,int p){
    t[p].l=l,t[p].r=r;
    t[p].tag=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
}
void modify(int lx,int rx,int p){
    if(t[p].l==lx&&t[p].r==rx){
        t[p].tag++;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(rx<=mid)modify(lx,rx,p<<1);
    else if(lx>mid)modify(lx,rx,p<<1|1);
    else{
        modify(lx,mid,p<<1);
        modify(mid+1,rx,p<<1|1);
    }
}
void update_route(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]>=dep[top[y]]){
            modify(dfn[top[x]],dfn[x],1);
            x=f[top[x]];
        }else{
            modify(dfn[top[y]],dfn[y],1);
            y=f[top[y]];
        }
    } 
    if(dep[x]<dep[y])modify(dfn[x]+1,dfn[y],1);
    else modify(dfn[y]+1,dfn[x],1);
}
int query(int x,int p){
    if(t[p].l==t[p].r)return t[p].tag;
    int ans=t[p].tag;
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid)ans+=query(x,p<<1);
    else ans+=query(x,p<<1|1);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    while(m--){
        char opt[5];
        int u,v;
        scanf("%s%d%d",opt,&u,&v);
        if(opt[0]=='P'){
            update_route(u,v);
        }else{
            if(dep[u]<dep[v])swap(u,v);
            printf("%d\n",query(dfn[u],1));
        }
    }
    return 0;
}