SDOI 2014 旅行

洛谷传送门

JDOJ传送门

Description

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教。

S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在S国的历史上常会发生以下几种事件：
• "CC x c"：城市x的居民全体改信了c教；
• "CW x w"：城市x的评级调整为w；
• "QS x y"：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
• "QM x y"：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。

为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

Input

输入的第一行包含整数N,Q，依次表示城市数和事件数。
接下来N行，第i+1行两个整数Wi,Ci依次表示记录开始之前，城市i的评级和信仰。
接下来N-1行每行两个整数x,y表示一条双向道路。
接下来Q行，每行一个操作，格式如上所述。

Output

对每个QS和QM事件，输出一行，表示旅行者记下的数字。

Sample Input

5 6 3 1 2 3 1 2 3 3 5 1 1 2 1 3 3 4 3 5 QS 1 5 CC 3 1 QS 1 5 CW 3 3 QS 1 5 QM 2 4

Sample Output

8 9 11 3

HINT

下表中C表示宗教总数。

数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于104的正整数，且宗教值不大于C。

题解：

树链剖分+动态开点

如果树链剖分不会的话请走这边：

详解树链剖分

浅谈动态开点线段树

题意为给定一棵树，对树上节点赋值+染色。每次操作更改点权或更改颜色，每次询问求路径最大值或路径权值和。

首先简化问题，假如没有染色的话，这就是树剖的板子题：把树上节点用树链剖分来映射到一段区间上，然后通过维护线段树来解决问题。不懂的见树剖讲解。

之后考虑如何染色。暴力的想法是，开色数棵线段树，但是一看不行，因为色数是10^5的。于是本能想到优化空间的好帮手：动态开点。对想法进行验证，发现每次操作并不需要完全使用所有节点，所以动态开点是完全可行的，每次修改的时空复杂度是\(O(\log N)\)，可过。

注意一下，有些同学说这个叫主席树，但是其实这个并不是主席树。主席树的特点是多棵线段树有共用节点。但是这道题并没有这个共用的点，每棵线段树是完全相互独立的。所以它不是主席树。

于是我们得出了结论：这道题是动态开点+树剖的板子题。（逃

于是这道题的难点变成了代码实现。需要注意的有几个点：

因为是多棵线段树，所以要开一个数组root来记录每棵线段树的根是谁。

因为是动态开点，所以一开始不需要建全树，对每个点进行修改即可。

因为权值都为正，所以在变更宗教的时候不需要把原来宗教的节点删除，直接置零即可。

代码如下：

#include<cstdio>
#include<algorithm>
#include<cctype>
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e5+10;
int n,q;
int w[maxn],c[maxn];
int tot,to[maxn<<1],nxt[maxn<<1],head[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<48||ch>57){if (ch=='-') f=-1;ch=getchar();}
	while (ch>=48&&ch<=57){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int cnt,fa[maxn],son[maxn],size[maxn],top[maxn],wa[maxn],id[maxn],deep[maxn];
int root[maxn],num;
struct node
{
    int mx,sum,lson,rson;
}t[maxn*42];
void dfs1(int x,int f)
{
    fa[x]=f;
    deep[x]=deep[f]+1;
    size[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==f)
            continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(!son[x]||size[y]>size[son[x]])
            son[x]=y;
    }
}
void dfs2(int x,int t)
{
    id[x]=++cnt;
    top[x]=t;
    if(!son[x])
        return;
    dfs2(son[x],t);
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==fa[x]||y==son[x])
            continue;
        dfs2(y,y);
    }
}
void pushup(int pos)
{
    t[pos].mx=max(t[t[pos].lson].mx,t[t[pos].rson].mx);
    t[pos].sum=t[t[pos].lson].sum+t[t[pos].rson].sum;
}
void update(int &pos,int l,int r,int x,int k)
{
    int mid=(l+r)>>1;
    if(!pos)
        pos=++num;
    if(l==r)
    {
        t[pos].mx=t[pos].sum=k;
        return;
    }
    if(x<=mid)
        update(t[pos].lson,l,mid,x,k);
    else
        update(t[pos].rson,mid+1,r,x,k);
    pushup(pos);
}
int query1(int pos,int l,int r,int x,int y)
{
    int ret=0;
    int mid=(l+r)>>1;
    if(x<=l && r<=y)
        return t[pos].sum;
    if(x<=mid)
        ret+=query1(t[pos].lson,l,mid,x,y);
    if(y>mid)
        ret+=query1(t[pos].rson,mid+1,r,x,y);
    return ret;
}
int query2(int pos,int l,int r,int x,int y)
{
    int ret=-10000000;
    int mid=(l+r)>>1;
    if(x<=l && r<=y)
        return t[pos].mx;
    if(x<=mid)
        ret=max(ret,query2(t[pos].lson,l,mid,x,y));
    if(y>mid)
        ret=max(ret,query2(t[pos].rson,mid+1,r,x,y));
    return ret;
}
int q1(int x,int y,int k)
{
    int ret=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);
        ret+=query1(root[k],1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])
        swap(x,y);
    ret+=query1(root[k],1,n,id[y],id[x]);
    return ret;
}
int q2(int x,int y,int k)
{
    int ret=-10000000;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);
        ret=max(ret,query2(root[k],1,n,id[top[x]],id[x]));
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])
        swap(x,y);
    ret=max(ret,query2(root[k],1,n,id[y],id[x]));
    return ret;
}
int main()
{
    n=read();q=read();
    for(int i=1;i<=n;i++)
        w[i]=read(),c[i]=read();
    for(int i=1;i<n;i++)
    {
        int a,b;
        a=read();b=read();
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=n;i++)
        update(root[c[i]],1,n,id[i],w[i]);
    while(q--)
    {
        char opt[5];
        int x,y;
        scanf("%s",opt);
        x=read();y=read();
        if(opt[1]=='C')
        {
            update(root[c[x]],1,n,id[x],0);
            c[x]=y;
            update(root[c[x]],1,n,id[x],w[x]);
        }
        else if(opt[1]=='W')
        {
            update(root[c[x]],1,n,id[x],y);
            w[x]=y;
        }
        else if(opt[1]=='S')
            printf("%d\n",q1(x,y,c[x]));
        else
            printf("%d\n",q2(x,y,c[x]));
    }
    return 0;
}