BZOJ 4999 This Problem Is Too Simple!

题目名字持续嘲讽……
非常套路。

首先考虑对每个颜色开一棵线段树，然后树剖维护即可。
这个想法非常显然（O(nlog2n)），但是有更好的做法。

发现每种操作最多涉及两种颜色（删掉原来的，添加新的），所以我们可以对每种颜色独立讨论。
那么问题变成树上单点修改，路径查询。
这个用 DFS 序 + 树状数组就可以做到 O(nlogn) 了。

以下代码为某 naive 爆的两只 log 做法。

代码：

#include <cstdio>
#include <algorithm>
#include <tr1/unordered_map>
#define ls seg[p].lson
#define rs seg[p].rson
using namespace std;
using namespace tr1;

const int BUFF_SIZE = 3 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 1e5;
const int Q = 2e5;
int n,q;
int to[(N << 1) + 10],pre[(N << 1) + 10],first[N + 10];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v;
    pre[tot] = first[u];
    first[u] = tot;
}
unordered_map<int,int> col_id;
int col_tot;
int rt[N + Q + 10],a[N + 10];
struct segnode
{
    int sum,lson,rson;
} seg[((N + Q) << 5) + 10];
void modify(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    if(tl == tr)
    {
        seg[p].sum += k;
        return ;
    }
    int mid = tl + tr >> 1;
    if(x <= mid)
        modify(x,k,ls,tl,mid);
    else
        modify(x,k,rs,mid + 1,tr);
    seg[p].sum = seg[ls].sum + seg[rs].sum;
}
int query(int l,int r,int p,int tl,int tr)
{
    if(!p)
        return 0;
    if(l <= tl && tr <= r)
        return seg[p].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query(l,r,ls,tl,mid);
    if(r > mid)
        ret += query(l,r,rs,mid + 1,tr);
    return ret;
}
int fa[N + 10],dep[N + 10],sz[N + 10],son[N + 10],top[N + 10],id[N + 10],rk[N + 10];
void dfs1(int p)
{
    sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs1(to[i]),sz[p] += sz[to[i]];
            if(!son[p] || sz[to[i]] > sz[son[p]])
                son[p] = to[i];
        }
}
void dfs2(int p)
{
    static int tot = 0;
    rk[id[p] = ++tot] = p;
    if(!son[p])
        return ;
    top[son[p]] = top[p];
    dfs2(son[p]);
    for(register int i = first[p];i;i = pre[i])
        if(!top[to[i]])
            top[to[i]] = to[i],dfs2(to[i]);
}
int answer(int x,int y,int k)
{
    int ret = 0;
    while(top[x] ^ top[y])
        dep[top[x]] > dep[top[y]] ? (ret += query(id[top[x]],id[x],rt[col_id[k]],1,n),x = fa[top[x]]) : (ret += query(id[top[y]],id[y],rt[col_id[k]],1,n),y = fa[top[y]]);
    if(dep[x] > dep[y])
        swap(x,y);
    ret += query(id[x],id[y],rt[col_id[k]],1,n);
    return ret;
}
int main()
{
    read(n),read(q);
    for(register int i = 1;i <= n;++i)
        read(a[i]);
    int u,v;
    for(register int i = 1;i < n;++i)
        read(u),read(v),add(u,v),add(v,u);
    dep[1] = top[1] = 1,dfs1(1),dfs2(1);
    for(register int i = 1;i <= n;++i)
    {
        if(!col_id.count(a[i]))
            col_id[a[i]] = ++col_tot;
        modify(id[i],1,rt[col_id[a[i]]],1,n);
    }
    while(q--)
    {
        char op = 0;
        while((op ^ 'Q') && (op ^ 'C'))
            op = gc();
        int x,y,z;
        if(op == 'Q')
        {
            read(x),read(y),read(z);
            if(!col_id.count(z))
                puts("0");
            else
                printf("%d\n",answer(x,y,z));
        }
        else
        {
            read(x),read(y);
            modify(id[x],-1,rt[col_id[a[x]]],1,n);
            a[x] = y;
            if(!col_id.count(a[x]))
                col_id[a[x]] = ++col_tot;
            modify(id[x],1,rt[col_id[a[x]]],1,n);
        }
    }
}