树剖求调

#include<cstdio>
const int N=100010;
struct edge
{
    int v;
    int nxt;
}e[N<<1];
int head[N];
int tot;
void add(int u,int v)
{
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int n,m;
int fa[N];
int son[N];
int size[N];
int dep[N];
void dfs1(int u,int f)
{
    size[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==f) continue;
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v,u);
        size[v]+=size[u];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
int id[N];
int top[N];
int total;
void dfs2(int u,int t)
{
    id[u]=++total;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
struct seg
{
    struct node
    {
        int l;
        int r;
        int val;
        int lz;
    }t[N<<2];
    #define ls k<<1
    #define rs k<<1|1
    void pushup(int k)
    {
        t[k].val=t[ls].val+t[rs].val;
    }
    void pushdown(int k)
    {
        if(!t[k].lz) return ;
        t[ls].lz+=t[k].lz;
        t[rs].lz+=t[k].lz;
        t[ls].val+=t[k].lz*(t[ls].r-t[ls].l+1);
        t[rs].val+=t[k].lz*(t[rs].r-t[rs].l+1);
        t[k].lz=0;
    }
    void build(int k,int l,int r)
    {
        t[k].l=l,t[k].r=r;
        if(l==r) return ;
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
    }
    void update(int k,int l,int r,int num)
    {
        if(t[k].l>=l&&t[k].r<=r)
        {
            t[k].lz+=num;
            t[k].val+=num*(t[k].r-t[k].l+1);
            return ;
        }
        pushdown(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(l<=mid) update(ls,l,r,num);
        if(r>mid)update(rs,l,r,num);
        pushup(k);
    }
    int query(int k,int x)
    {
        if(t[k].l==t[k].r) return t[k].val;
        pushdown(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(x<=mid) return query(ls,x);
        if(x>mid) return query(rs,x);
    }
}tree;
void swap(int &x,int &y)
{
    int tmp=x;
    x=y;
    y=tmp;
}
void upd(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        tree.update(1,id[top[x]],id[x],1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    tree.update(1,id[x]+1,id[y],1);
}
int que(int x,int y)
{
    if(fa[x]==y) return tree.query(1,id[x]);
    else return tree.query(1,id[y]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=n-1;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs1(1,0);
    dfs2(1,1);
    tree.build(1,1,n);
    while(m--)
    {
        char op;
        int x,y;
        scanf(" %c %d%d",&op,&x,&y);
        if(op=='P') upd(x,y);
        else printf("%d\n",que(x,y));
    }
    return 0;
}

全WA