天若有情天亦老 我为$Claris + 1s$

然而我并不能去R2 233333333333333

懵逼的 题目

扯淡的 题解

sb题…我去年怎么想到splay上面去了(可能是考虑删除和插入? 但是这题又不卡空间…lxl: 哦?)…

动态开点, 开$10^5$棵线段树维护每一种宗教就行了…

沙茶的 代码

/**************************************************************
    Problem: 3531
    User: Cansult
    Language: C++
    Result: Accepted
    Time:8952 ms
    Memory:52392 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define pii pair<int, int>
const int troot = 1;
using namespace std;
struct edg
{
    int from, to, next;
}tb[MAXN << 1];
int tg[MAXN];
struct tnode
{
    int zh, reli, deep, top, fa, hs, size, begin, end;
}ta[MAXN];
pii a[MAXN];
int n, cnta;
struct node
{
    int le, ri, zh, sum, ls, rs;
}b[MAXN << 4];
int cntb, root[MAXN];
void adn(int from, int to)
{
    static int cntt = -1;
    tb[++cntt].next = tg[from];
    tb[cntt].from = from;
    tb[cntt].to = to;
    tg[from] = cntt;
}
void push_up(int dq)
{
    b[dq].zh = max(b[b[dq].ls].zh, b[b[dq].rs].zh);
    b[dq].sum = b[b[dq].ls].sum + b[b[dq].rs].sum;
}
void xg(int& dq, int le, int ri, int wz, int zh)
{
    if(!dq)
        dq = ++cntb;
    b[dq].le = le, b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].sum = b[dq].zh = zh;
        return ;
    }
    int mi = (le + ri) >> 1;
    if (wz > mi)
        xg(b[dq].rs, mi + 1, ri, wz, zh);
    else
        xg(b[dq].ls, le, mi, wz, zh);
    push_up(dq);
}
int cxmax(int dq, int le, int ri)
{
    if (!dq)
        return 0;
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        return cxmax(b[dq].rs, le, ri);
    else if (ri <= mi)
        return cxmax(b[dq].ls, le, ri);
    else
        return max(cxmax(b[dq].ls, le, mi), cxmax(b[dq].rs, mi + 1, ri));
}
int cxsum(int dq, int le, int ri)
{
    if (!dq)
        return 0;
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].sum;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        return cxsum(b[dq].rs, le, ri);
    else if (ri <= mi)
        return cxsum(b[dq].ls, le, ri);
    else
        return cxsum(b[dq].ls, le, mi) + cxsum(b[dq].rs, mi + 1, ri);
}
void init(int dq, int deep)
{
    ta[dq].deep = deep;
    ta[dq].size = 1;
    for (int i = tg[dq]; ~i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, deep + 1);
            ta[dq].size += ta[tb[i].to].size;
            if (ta[tb[i].to].size > ta[ta[dq].hs].size)
                ta[dq].hs = tb[i].to;
        }
}
void dfs(int dq)
{
    a[ta[dq].begin = ++cnta] = make_pair(ta[dq].reli, ta[dq].zh);
    if (ta[dq].hs)
        ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
    for (int i = tg[dq]; ~i; i = tb[i].next)
        if (tb[i].to != ta[dq].hs && tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    ta[dq].end = cnta;
}
void js()
{
    for (int i = 1; i <= n; i++)
        xg(root[a[i].first], 1, n, i, a[i].second);
}
int solvemax(int x, int y)
{
    int re = -INF, dqroot = root[ta[x].reli];
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep)
            swap(x, y);
        re = max(re, cxmax(dqroot, ta[ta[x].top].begin, ta[x].begin));
        x = ta[ta[x].top].fa;
    }
    if (ta[x].deep > ta[y].deep)
        swap(x, y);
    re = max(re, cxmax(dqroot, ta[x].begin, ta[y].begin));
    return re;
}
int solvesum(int x, int y)
{
    int re = 0, dqroot = root[ta[x].reli];
    while (ta[x].top != ta[y].top)
    {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep)
            swap(x, y);
        re += cxsum(dqroot, ta[ta[x].top].begin, ta[x].begin);
        x = ta[ta[x].top].fa;
    }
    if (ta[x].deep > ta[y].deep)
        swap(x, y);
    re += cxsum(dqroot, ta[x].begin, ta[y].begin);
    return re;
}
int main()
{
//    cout << "Hello world!" << endl;
    memset(tg, -1, sizeof(tg));
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &ta[i].zh, &ta[i].reli);
    for (int i = 1; i < n; i++)
    {
        int srx, sry;
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    init(troot, 1);
    dfs(troot);
    js();
    for (int i = 1; i <= q; i++)
    {
        char sre[4];
        int srx, sry;
        scanf("%s%d%d", sre, &srx, &sry);
        if (sre[0] == 'Q')
        {
            if (sre[1] == 'S')
                printf("%d\n", solvesum(srx, sry));
            else
                printf("%d\n", solvemax(srx, sry));
        }
        else
        {
            if (sre[1] == 'C')
                xg(root[ta[srx].reli], 1, n, ta[srx].begin, 0), xg(root[ta[srx].reli = sry], 1, n, ta[srx].begin, ta[srx].zh);
            else
                xg(root[ta[srx].reli], 1, n, ta[srx].begin, ta[srx].zh = sry);
        }
    }
    return 0;
}

/*
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
*/

By sb Cansult