https://loj.ac/problem/2195

题目描述

  给出一棵树，每个节点有权值和颜色，要求维护四个操作：\(①\)改变节点\(x\)的颜色为\(c\)；\(②\)改变节点\(x\)的权值为\(w\)；\(③\)询问从\(a\)到\(b\)的路径中颜色和\(a\)相同的点的权值和；\(④\)询问从\(a\)到\(b\)的路径中颜色与\(a\)相同的点的权值最大值。

思路

  比较显然需要用树链剖分，我们只要考虑如何维护信息。还是看做序列考虑，比较显然的是对每个颜色都开一棵线段树维护，不过这样空间显然难以支撑。我们考虑存在一个数组内，但对于每一棵树实行动态开点，每个节点记录一下左儿子节点和右儿子节点，实现删除和新建节点即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

struct Segment
{
    int sum,maxx,lc,rc;
}T[N<<4];
int idx;
void pushup(int k)
{
    T[k].sum=T[T[k].lc].sum+T[T[k].rc].sum;
    T[k].maxx=max(T[T[k].lc].maxx,T[T[k].rc].maxx);
}
void add(int &k,int l,int r,int pos,int v)
{
    if(!k)k=++idx;
    if(l==r)
    {
        T[k].sum=T[k].maxx=v;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid)add(T[k].lc,l,mid,pos,v);
    else add(T[k].rc,mid+1,r,pos,v);
    pushup(k);
}
void f_delete(int &k,int l,int r,int pos)
{
    if(!k)return ;
    if(l==r)
    {
        T[k].sum=T[k].maxx=0;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid)f_delete(T[k].lc,l,mid,pos);
    else f_delete(T[k].rc,mid+1,r,pos);
    pushup(k);
}
int querysum(int &k,int l,int r,int x,int y)
{
    if(!k)return 0;
    if(l>=x&&r<=y)
        return T[k].sum;
    int mid=l+r>>1,ans=0;
    if(x<=mid)ans+=querysum(T[k].lc,l,mid,x,y);
    if(y>mid)ans+=querysum(T[k].rc,mid+1,r,x,y);
    return ans;
}
int querymax(int &k,int l,int r,int x,int y)
{
    if(!k)return 0;
    if(l>=x&&r<=y)
        return T[k].maxx;
    int mid=l+r>>1,ans=0;
    if(x<=mid)ans=max(ans,querymax(T[k].lc,l,mid,x,y));
    if(y>mid)ans=max(ans,querymax(T[k].rc,mid+1,r,x,y));
    return ans;
}

int nxt[N<<1],to[N<<1],tot,head[N];
void add_edge(int x,int y)
{
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}

int fa[N],siz[N],dep[N],son[N],top[N];
int seg[N<<4],rev[N<<4];
void dfs1(int u,int father)
{
    siz[u]=1;fa[u]=father;
    dep[u]=dep[father]+1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==father)continue ;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int father)
{
    if(son[u])
    {
        seg[son[u]]=++seg[0];
        rev[seg[0]]=son[u];
        top[son[u]]=top[u];
        dfs2(son[u],u);
    }
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(top[v])continue ;
        seg[v]=++seg[0];
        rev[seg[0]]=v;
        top[v]=v;
        dfs2(v,u);
    }
}
int cnt,n;
void asksum(int x,int y,int k)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
        cnt+=querysum(k,1,n,seg[fx],seg[x]);
        x=fa[fx];fx=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    cnt+=querysum(k,1,n,seg[x],seg[y]);
}
void askmax(int x,int y,int k)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
        cnt=max(cnt,querymax(k,1,n,seg[fx],seg[x]));
        x=fa[fx];fx=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    cnt=max(cnt,querymax(k,1,n,seg[x],seg[y]));
}

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void writeln(int x)
{
    write(x);
    putchar('\n');
}

int w[N],c[N],mp[N];
int main() 
{
    n=read();
    int q=read();
    for(int i=1;i<=n;i++)
        w[i]=read(),c[i]=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);add_edge(y,x);
    }
    dfs1(1,0);
    seg[0]=seg[1]=rev[1]=top[1]=1;
    dfs2(1,0);
//  for(int i=1;i<=n;i++)
//      printf("%d\n",seg[i]);
    for(int i=1;i<=n;i++)
        add(mp[c[i]],1,n,seg[i],w[i]);
/*  printf("\n");
    for(int i=1;i<=n;i++)
        printf("%d %d\n",c[i],querymax(mp[c[i]],1,n,1,n));
    printf("\n");*/
    while(q--)
    {
        char s[10];
        scanf(" %s",s);
        int x=read(),y=read();
        if(s[1]=='C')
        {
            f_delete(mp[c[x]],1,n,seg[x]);
            c[x]=y;
            add(mp[c[x]],1,n,seg[x],w[x]);
        }
        else if(s[1]=='W')
        {
            f_delete(mp[c[x]],1,n,seg[x]);
            w[x]=y;
            add(mp[c[x]],1,n,seg[x],w[x]);
        }
        else if(s[1]=='S')
        {
            cnt=0;
            asksum(x,y,mp[c[x]]);
            writeln(cnt);
        }
        else
        {
            cnt=0;
            askmax(x,y,mp[c[x]]);
            writeln(cnt);
        }
    }
    return 0;
}