题目描述

给定一棵 $n$ 个点的树，每个点有一种颜色 $c$ 和一个权值 $w$，共进行 $m$ 次操作
$n \leq 10^5, m \leq 10^5, c_i \leq 10^5$

• 修改某一点的颜色
• 修改某一点的权值
• 查询简单路径上某颜色的最大权值
• 查询简单路径上某颜色的权值之和

树链剖分 + 动态开点线段树

动态开点的线段树的l, r存左右子节点的编号

每次操作最多会新建 $logn$ 个节点，所以最多会有 $(n + m)logn$ 个节点，空间复杂度 $(n + m)logn$

查询时把区间左右边界left, right和查询区间边界l, r同时往下传

记得修改某个城市的宗教信仰时要清空这个点之前所在节点的权值

时间复杂度 $O(mlog^2n)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = N * 2;

struct Node{
    int l, r;
    int d, sum;
}tr[N * 18];

int n, m;
int col[N], w[N];       //  某个城市的人信什么教，评级是多少
int root[N], cham;

void pushup(int u)
{
    tr[u].d = max(tr[tr[u].l].d, tr[tr[u].r].d);
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

void update(int u, int l, int r, int x, int w)
{
    if(l == x and r == x)
    {
        tr[u].d = tr[u].sum = w;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid)
    {
        if(!tr[u].l)  tr[u].l = ++ cham;
        update(tr[u].l, l, mid, x, w);
    }
    else
    {
        if(!tr[u].r)  tr[u].r = ++ cham;
        update(tr[u].r, mid + 1, r, x, w);
    }
    pushup(u);
}

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int f[N], dep[N], sz[N], son[N];
void dfs1(int u, int fa)
{
    f[u] = fa, dep[u] = dep[fa] + 1, sz[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        dfs1(j, u);
        sz[u] += sz[j];
        if(sz[j] > sz[son[u]])  son[u] = j;
    }
}

int id[N], rk[N], top[N], tot;
void dfs2(int u, int t)
{
    id[u] = ++ tot, rk[tot] = u, top[u] = t;
    if(son[u])  dfs2(son[u], t);
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == f[u] or j == son[u])  continue;
        dfs2(j, j);
    }
}

int querysum(int u, int left, int right, int l, int r)
{
    if(!u)  return 0;
    if(left >= l and right <= r)  return tr[u].sum;

    int res = 0;
    int mid = left + right >> 1;
    if(l <= mid)  res += querysum(tr[u].l, left, mid, l, r);
    if(r > mid)  res += querysum(tr[u].r, mid + 1, right, l, r);
    return res;
}

int qs(int a, int b, int c)
{
    int res = 0;
    while(top[a] != top[b])
    {
        if(dep[top[a]] < dep[top[b]])  swap(a, b);
        res += querysum(root[c], 1, n, id[top[a]], id[a]);
        a = f[top[a]];
    }
    if(dep[a] > dep[b])  swap(a, b);
    res += querysum(root[c], 1, n, id[a], id[b]);
    return res;
}

int querymax(int u, int left, int right, int l, int r)
{
    if(!u)  return 0;
    if(left >= l and right <= r)  return tr[u].d;

    int res = 0;
    int mid = left + right >> 1;
    if(l <= mid)  res = querymax(tr[u].l, left, mid, l, r);
    if(r > mid)  res = max(res, querymax(tr[u].r, mid + 1, right, l, r));
    return res;
}

int qm(int a, int b, int c)
{
    int res = 0;
    while(top[a] != top[b])
    {
        if(dep[top[a]] < dep[top[b]])  swap(a, b);
        res = max(res, querymax(root[c], 1, n, id[top[a]], id[a]));
        a = f[top[a]];
    }
    if(dep[a] > dep[b])  swap(a, b);
    res = max(res, querymax(root[c], 1, n, id[a], id[b]));
    return res;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)  scanf("%d%d", &w[i], &col[i]);

    for(int i = 1; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs1(1, 0);
    dfs2(1, 1);

    for(int i = 1; i <= n; i ++)
    {
        if(!root[col[i]])  root[col[i]] = ++ cham;
        update(root[col[i]], 1, n, id[i], w[i]);
    }

    while(m --)
    {
        char op[3];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(op[1] == 'C')
        {
            //  城市a改信b教
            update(root[col[a]], 1, n, id[a], 0);
            col[a] = b;
            if(!root[col[a]])  root[col[a]] = ++ cham;
            update(root[col[a]], 1, n, id[a], w[a]);
        }
        else if(op[1] == 'W')
        {
            //  城市a的评级改为b
            w[a] = b;
            update(root[col[a]], 1, n, id[a], w[a]);
        }
        else if(op[1] == 'S')
        {
            //  求路径上信col[a]教的权值和
            printf("%d\n", qs(a, b, col[a]));
        }
        else
        {
            printf("%d\n", qm(a, b, col[a]));
        }
    }
    return 0;
}