[BZOJ3531] [Sdoi 2014] 여행 나무 사슬 분할.

광고:

#include <stdio.h>
int main()
{
    puts("       [vmurder]  ");
    puts("  ：blog.csdn.net/vmurder/article/details/44026729");
}

문제 풀이:

코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define LOGN 20
#define ls s[note].l
#define rs s[note].r
#define inf 0x3f3f3f3f
using namespace std;
struct KSD
{
    int v,next;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int n,m;
int crs[N],src[N];

int dep[N],top[N],pos[N];
int fa[N],son[N];
int dfs1(int x,int p)
{
    int i,v,temp,mx=0,size=1;
    dep[x]=dep[p]+1;
    fa[x]=p;
    for(i=head[x];i;i=e[i].next)
    {
        v=e[i].v;
        if(v==p)continue;
        temp=dfs1(v,x);
        size+=temp;
        if(mx<temp)mx=temp,son[x]=v;
    }
    return size;
}
void dfs2(int x,int p,int t)
{
    top[x]=t;
    pos[x]=++cnt;
    int i,v;
    if(son[x])dfs2(son[x],x,t);
    for(i=head[x];i;i=e[i].next)
    {
        v=e[i].v;
        if(v==son[x]||v==p)continue;
        dfs2(v,x,v);
    }
}
struct Segment_Tree
{
    int l,r;
    int mx,sum;
}s[N*LOGN*5];
int root[N],num;
inline void pushup(int note)
{
    s[note].mx=max(s[ls].mx,s[rs].mx);
    s[note].sum=s[ls].sum+s[rs].sum;
}
void add(int &note,int L,int R,int x,int w)
{
    if(!note)note=++num;
    if(L==R)
    {
        s[note].mx=s[note].sum=w;
        return ;
    }
    int mid=L+R>>1;
    if(x<=mid)add(ls,L,mid,x,w);
    else add(rs,mid+1,R,x,w);
    pushup(note);
}
void remove(int note,int L,int R,int x)
{
    //if(!note)note=++num;
    if(L==R)
    {
        s[note].mx=s[note].sum=0;
        return ;
    }
    int mid=L+R>>1;
    if(x<=mid)remove(ls,L,mid,x);
    else remove(rs,mid+1,R,x);
    pushup(note);
}
int query(int note,int L,int R,int l,int r,int f)
{
    if(!note)return 0;
    if(L==l&&r==R)
    {
        if(f)return s[note].mx;
        else return s[note].sum;
    }
    int mid=L+R>>1;
    if(r<=mid)return query(ls,L,mid,l,r,f);
    else if(l>mid)return query(rs,mid+1,R,l,r,f);
    else {
        int a=query(ls,L,mid,l,mid,f);
        int b=query(rs,mid+1,R,mid+1,r,f);
        if(f)return max(a,b);
        else return a+b;
    }
}
int QUERY(int a,int b,int f)
{
    int rt=root[crs[a]];
    int ans=0,temp;
    for(int A=top[a],B=top[b];A!=B;a=fa[A],A=top[a])
    {
        if(dep[A]<dep[B])swap(A,B),swap(a,b);
        temp=query(rt,1,n,pos[A],pos[a],f);
        if(f)ans=max(ans,temp);
        else ans+=temp;
    }
    if(dep[a]<dep[b])swap(a,b);
    temp=query(rt,1,n,pos[b],pos[a],f);
    if(f)ans=max(ans,temp);
    else ans+=temp;
    return ans;
}

char ss[5];
int main()
{
    freopen("test.in","r",stdin);
    int i,j,k;
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d%d",&src[i],&crs[i]);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    cnt=0;
    dfs1(1,0),dfs2(1,0,1);
    for(i=1;i<=n;i++)add(root[crs[i]],1,n,pos[i],src[i]);
    while(m--)
    {
        scanf("%s%d%d",ss,&a,&b);
        if(ss[1]=='C')
        {
            remove(root[crs[a]],1,n,pos[a]);
            add(root[b],1,n,pos[a],src[a]);
            crs[a]=b;
        }
        else if(ss[1]=='W')
        {
            add(root[crs[a]],1,n,pos[a],b);
            src[a]=b;
        }
        else if(ss[1]=='S')printf("%d
",QUERY(a,b,0));
        else printf("%d
",QUERY(a,b,1));
    }
    return 0;
}