题解：UVA12424 Answering Queries on a Tree

· · 题解

典中典。

由于颜色数极少，所以可以对于每种颜色都开一个线段树进行维护。

  1. 对于操作 0，将 C_u 所对应的线段树的节点点权 -1，将 c 所对应的线段树的节点点权 +1。
  2. 对于每一种颜色进行一遍查询再求最值。

code：

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define N 100009
#define ls(i) (i << 1)
#define rs(i) ((i << 1) | 1)
#define sp(i,j) i^=j,j^=i,i^=j
int n, m;
struct V{
    vector<int> e;
    int size;
    int top;
    int h;
    int d;
    int id;
    int fa;
    int son;
}v[N];
int rk[N];
struct TREE{
    struct V{
        int l, r, d;
    }tree[(N << 2)];
    inline void build(int i, int l, int r, int x) {
        tree[i].l = l, tree[i].r = r, tree[i].d = 0;
        if(l == r) {
            tree[i].d = v[rk[l]].d == x;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(i), l, mid, x), build(rs(i), mid + 1, r, x);
        tree[i].d = tree[ls(i)].d + tree[rs(i)].d;
    }
    inline void change(int i, int x, int y) {
        if(tree[i].l == tree[i].r) {
            tree[i].d = y;
            return;
        }
        int mid = (tree[i].l + tree[i].r) >> 1;
        if(x <= mid) change(ls(i), x, y);
        else change(rs(i), x, y);
        tree[i].d = tree[ls(i)].d + tree[rs(i)].d;
    }
    inline int ask(int i, int l, int r) {
        if(l <= tree[i].l && tree[i].r <= r) return tree[i].d;
        int mid = (tree[i].l + tree[i].r) >> 1, t = 0;
        if(l <= mid) t += ask(ls(i), l, r);
        if(mid < r) t += ask(rs(i), l, r);
        return t;
    }
}xds[11];
inline void dfs(int u, int fa, int h) {
    v[u].h = h;
    v[u].fa = fa;
    v[u].size = 1;
    int cnt = -114514;
    for(auto to: v[u].e) {
        if(to == fa) continue;
        dfs(to, u, h + 1);
        v[u].size += v[to].size;
        if(cnt < v[to].size) v[u].son = to, cnt = v[to].size; 
    }
}
int res = 0;
inline void dfs2(int u, int top) {
    v[u].top = top;
    v[u].id = ++res;
    rk[res] = u;
    if(!v[u].son) return;
    dfs2(v[u].son, top);
    for(auto to: v[u].e) {
        if(to == v[u].fa) continue;
        if(to == v[u].son) continue;
        dfs2(to, to);
    }
}
inline int ask(int x, int y, int z) {
    int ans = 0;
    while(v[x].top ^ v[y].top) {
        if(v[v[x].top].h < v[v[y].top].h) sp(x, y);
        ans += xds[z].ask(1, v[v[x].top].id, v[x].id);
        x = v[v[x].top].fa;
    }
    if(v[x].h > v[y].h) sp(x, y);
    ans += xds[z].ask(1, v[x].id, v[y].id);
    return ans;
}
inline void sovel() {
    cin >> n >> m;
    fill(v + 1, v + n + 1, v[0]);
    res = 0;
    for(int i = 1; i <= n; i++)
        cin >> v[i].d;
    for(int i = 1, _u, _v; i < n; i++) {
        cin >> _u >> _v;
        v[_u].e.push_back(_v);
        v[_v].e.push_back(_u);
    }
    dfs(1, 0, 1);
    dfs2(1, 1);
    for(int i = 1; i <= 10; i++)
        xds[i].build(1, 1, n, i);
    while(m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 0) {
            xds[v[x].d].change(1,v[x].id,0);
            xds[y].change(1,v[x].id,1);
            v[x].d = y;
        } else {
            int maxn = 0;
            for(int i = 1; i <= 10; i++) {
                maxn = max(maxn, ask(x, y, i));
            }
            cout << maxn << "\n";
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _T = 1;
    cin >> _T;
    while(_T--) {
        sovel();
    }
    return 0;
}

说句闲话：因为我不会卡常，于是我用了火车头就过了。