BZOJ3531 SDOI2014 旅行

#include<bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
#define ll long long 
#define pb push_back
using namespace std;
const int maxn=1e5+100;
int fir[maxn],nxt[maxn*2],to[maxn*2];
int depth[maxn],top[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn];
int w[maxn],root[maxn],c[maxn];
struct node
{
    int l,r;
    int sum,mx;
}no[maxn*40];
int tot=0,cnt=0,cns=0;
void add_e(int x,int y)
{
    ++cnt;nxt[cnt]=fir[x];fir[x]=cnt;to[cnt]=y;
    ++cnt;nxt[cnt]=fir[y];fir[y]=cnt;to[cnt]=x;
}
void dfs1(int x,int f)
{
    depth[x]=depth[f]+1;
    fa[x]=f;
    siz[x]=1;
    int maxx=0;
    fa[x]=f;
    for(int i=fir[x];i;i=nxt[i])
    {
        int v=to[i];
        if(v==f)continue;
        dfs1(v,x);
        siz[x]+=siz[v];
        if(siz[v]>maxx)
        {
            maxx=siz[v];
            son[x]=v;
        }
    }
}
void dfs2(int x,int f)
{
    top[x]=f;
    id[x]=++tot;
    if(son[x])dfs2(son[x],f);
    for(int i=fir[x];i;i=nxt[i])
    {
        if(to[i]==fa[x]||to[i]==son[x])continue;
        dfs2(to[i],to[i]);
    }
}
void push_up(int x)
{
    no[x].sum=no[no[x].l].sum+no[no[x].r].sum;
    no[x].mx=max(no[no[x].l].mx,no[no[x].r].mx);
}
void build(int&x,int l,int r,int v,int pl)
{
    if(!x)x=++cns;
    if(l==r)
    {
        no[x].sum=no[x].mx=v;
        return;
    }
    int mid=(l+r)>>1;
    if(pl<=mid)build(no[x].l,l,mid,v,pl);
    else build(no[x].r,mid+1,r,v,pl);
    push_up(x);
}
int query_max(int x,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return no[x].mx;
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid)ans=max(ans,query_max(no[x].l,l,mid,L,R));
    if(R>mid)ans=max(ans,query_max(no[x].r,mid+1,r,L,R));
    return ans;     
}
int query_sum(int x,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return no[x].sum;
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid)ans+=query_sum(no[x].l,l,mid,L,R);
    if(R>mid)ans+=query_sum(no[x].r,mid+1,r,L,R);
    return ans;
}
int n,q;
char a[10];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);add_e(u,v);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=n;i++)build(root[c[i]],1,tot,w[i],id[i]);
    for(int i=1;i<=q;i++)
    {
        scanf("%s",a);
        if(a[0]==‘C‘&&a[1]==‘C‘)
        {
            scanf("%d%d",&u,&v);
            build(root[c[u]],1,tot,0,id[u]);
            build(root[v],1,tot,w[u],id[u]);
            c[u]=v;
        }
        if(a[0]==‘C‘&&a[1]==‘W‘)
        {
            scanf("%d%d",&u,&v);
            build(root[c[u]],1,tot,v,id[u]);
            w[u]=v;
        }
        if(a[0]==‘Q‘&&a[1]==‘S‘)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int ans=0;
            int sr=c[x];//这个地方一定要记录c[x]
            int tx=top[x],ty=top[y];
            while(tx!=ty)
            {
                if(depth[tx]<depth[ty])
                {
                    swap(x,y);swap(tx,ty);
                }
                ans+=query_sum(root[sr],1,tot,id[tx],id[x]);
                x=fa[tx];
                tx=top[x];
            }
            if(id[x]>id[y])swap(x,y);
            ans+=query_sum(root[sr],1,tot,id[x],id[y]);
            cout<<ans<<"\n";
        }
        if(a[0]==‘Q‘&&a[1]==‘M‘)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int ans=0;
            int sr=c[x];
            int tx=top[x],ty=top[y];
            while(tx!=ty)
            {
                if(depth[tx]<depth[ty])
                {
                    swap(x,y);swap(tx,ty);
                }
                ans=max(ans,query_max(root[sr],1,tot,id[tx],id[x]));
                x=fa[tx];
                tx=top[x];
            }
            if(id[x]>id[y])swap(x,y);
            ans=max(ans,query_max(root[sr],1,tot,id[x],id[y]));
            cout<<ans<<"\n";
        }
    }
}