Accepted/86328 kb/11992 ms

bzoj3531.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxs=4000000,maxn=100005;
//--线段树
struct tree{
    int l,r,c,m,s;
    tree(int _l=0,int _r=0,int _m=0,int _s=0):
        l(_l),r(_r),m(_m),s(_s){}
    //left right max sum
}t[maxs];
int tn;
//--end
//--树链剖分
vector<int>e[maxn];
vector<int>::iterator vi;
int pn;
int n,q;
int pos[maxn],c[maxn],w[maxn],ct[maxn];
int sz[maxn],fa[maxn],tp[maxn],hs[maxn],dp[maxn],qu[maxn];
int qf,qt;
//--end
void bfs()
{
    int u,v;
    dp[qu[qf=qt=1]=1]=1;
    for (;qf<=qt;qf++)
        for (vi=e[u=qu[qf]].begin();vi!=e[u].end();vi++)
            if (!dp[*vi])
                dp[qu[++qt]=*vi]=dp[fa[*vi]=u]+1;
    for (int i=qt;i>=1;i--)
    {
        sz[fa[qu[i]]]+=++sz[qu[i]];
        if (sz[qu[i]]>sz[hs[fa[qu[i]]]])
            hs[fa[qu[i]]]=qu[i];
    }
    for (int i=1;i<=qt;i++)
        if (!tp[u=qu[i]])
            for (v=u;v;v=hs[v])
            {
                tp[v]=u;
                pos[v]=++pn;
            }
}
void update(const int &x)
{
    t[x].m=max(t[t[x].l].m,t[t[x].r].m);
    t[x].s=t[t[x].l].s+t[t[x].r].s;
}
void CC(int &x,int l,int r,int pos,int wgt)
{
    if (!x)
        x=++tn;
    if (l==r)
    {
        t[x].m=t[x].s=wgt;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid)
        CC(t[x].l,l,mid,pos,wgt);
    if (pos>mid)
        CC(t[x].r,mid+1,r,pos,wgt);
    update(x);
}
int QS(int x,int l,int r,int ql,int qr)
{
    if (!x)
        return 0;
    if (ql<=l && r<=qr)
        return t[x].s;
    int mid=(l+r)/2,ans=0;
    if (ql<=mid)
        ans+=QS(t[x].l,l,mid,ql,qr);
    if (qr>mid)
        ans+=QS(t[x].r,mid+1,r,ql,qr);
    return ans;
}
int QM(int x,int l,int r,int ql,int qr)
{
    if (!x)
        return 0;
    if (ql<=l && r<=qr)
        return t[x].m;
    int mid=(l+r)/2,ans=0;
    if (ql<=mid)
        ans=max(ans,QM(t[x].l,l,mid,ql,qr));
    if (qr>mid)
        ans=max(ans,QM(t[x].r,mid+1,r,ql,qr));
    return ans;
}
int QS(int x,int y)
{
    int ans=0;
    int co=c[x];
    while (tp[x]!=tp[y])
        if (dp[tp[x]]>dp[tp[y]])
            ans+=QS(ct[co],1,n,pos[tp[x]],pos[x]),x=fa[tp[x]];
        else
            ans+=QS(ct[co],1,n,pos[tp[y]],pos[y]),y=fa[tp[y]];
    if (dp[x]>dp[y])
        ans+=QS(ct[co],1,n,pos[y],pos[x]);
    else
        ans+=QS(ct[co],1,n,pos[x],pos[y]);
    return ans;
}
int QM(int x,int y)
{
    int ans=0;
    int co=c[x];
    while (tp[x]!=tp[y])
        if (dp[tp[x]]>dp[tp[y]])
            ans=max(ans,QM(ct[co],1,n,pos[tp[x]],pos[x])),x=fa[tp[x]];
        else
            ans=max(ans,QM(ct[co],1,n,pos[tp[y]],pos[y])),y=fa[tp[y]];
    if (dp[x]>dp[y])
        ans=max(ans,QM(ct[co],1,n,pos[y],pos[x]));
    else
        ans=max(ans,QM(ct[co],1,n,pos[x],pos[y]));
    return ans;
}
int main()
{
    char op[5];
    int u,v;
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&w[i],&c[i]);
    for (int i=1;i<n;i++)
        scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
    bfs();
    for (int i=1;i<=n;i++)
        CC(ct[c[i]],1,n,pos[i],w[i]);
    for (int i=1;i<=q;i++)
    {
        scanf("%s%d%d",op,&u,&v);
        if (op[1]=='C')
            CC(ct[c[u]],1,n,pos[u],0),CC(ct[c[u]=v],1,n,pos[u],w[u]);
        else if (op[1]=='W')
            CC(ct[c[u]],1,n,pos[u],w[u]=v);
        else if (op[1]=='S')
            printf("%d\n",QS(u,v));
        else if (op[1]=='M')
            printf("%d\n",QM(u,v));
    }
    return 0;
}