蒟蒻31pts求调

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define N 100010

using namespace std;
struct node{
    ll to,nxt;
}e[N<<1];
int tot=0,head[N];
int top[N],siz[N],fa[N],dep[N],son[N];
int id[N],cnt=0;
ll a[N<<2],laz[N<<2];
int n,m;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(int u,int v){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void dfs1(int u,int f,int deep){
    fa[u]=f;
    dep[u]=deep;
    siz[u]=1;
    int maxson=-1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f) continue;
        dfs1(v,u,deep+1);
        siz[u]+=siz[v];
        if(siz[v]>maxson){
            maxson=siz[v];
            son[u]=v;
        }
    }
}
void dfs2(int u,int topf){
    id[u]=++cnt;
    top[u]=topf;
    if(!son[u]) return;
    dfs2(son[u],topf);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
ll res=0,ans=0;
void pushdown(int x,int len){
    laz[x<<1]+=laz[x];
    laz[x<<1|1]+=laz[x];
    a[x<<1]+=laz[x]*(len-(len>>1));
    a[x<<1|1]+=laz[x]*(len>>1);
    laz[x]=0;
}
void update(int x,int l,int r,int L,int R){
    if(L<=l && r<=R){
        a[x]+=r-l+1;
        laz[x]++;
        return;
    }
    if(laz[x]) pushdown(x,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(x<<1,l,mid,L,R);
    if(R>mid) update(x<<1|1,mid+1,r,L,R);
    a[x]=a[x<<1]+a[x<<1|1];
}
void query(int x,int l,int r,int L,int R){
    if(L<=l && r<=R){
        res+=a[x];
        return;
    }
    int mid=(l+r)>>1;
    if(laz[x]) pushdown(x,r-l+1);
    if(L<=mid) query(x<<1,l,mid,L,R);
    if(R>mid) query(x<<1|1,mid+1,r,L,R);
}
void ubian(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        update(1,1,n,id[top[x]]+1,id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    update(1,1,n,id[x]+1,id[y]);
}
ll qbian(int x,int y){
    ans=0;
    while(top[x]!=top[y]){
        res=0;
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        query(1,1,n,id[top[x]]+1,id[x]);
        x=fa[top[x]];
        ans+=res;
    }
    if(dep[x]>dep[y]) swap(x,y);
    res=0;
    query(1,1,n,id[x]+1,id[y]);
    ans+=res;
    return ans;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    while(m--){
        char c;
        cin>>c;
        int x=read(),y=read();
        if(c=='P'){
            ubian(x,y);
        }else{
            printf("%lld\n",qbian(x,y));
        }
    }
    return 0;
}