题解 CF620E 【New Year Tree】

蛮好玩的一道题 首先dfs序变成序列操作就不说了 考虑到颜色数比较少，我们可以将颜色数状压，维护一个$sum$表示颜色集合，上传的时候或一下就好了 代码： ```cpp #include<bits/stdc++.h> #define fo(i, a, b) for (int i = (a); i <= (b); ++i) #define fd(i, a, b) for (int i = (a); i >= (b); --i) #define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v) #define N 400005 #define pb push_back #define F first #define S second #define ll long long #define inf 1000000007 #define mp std::make_pair #define lowbit(x) (x & -x) #define ls (k << 1) #define rs (k << 1 | 1) int n, m, a[N], x, y, L[N], R[N], tim, ti[N], val, opt, tot; struct edge{ int nxt, v; }e[N << 1]; int head[N]; struct node{ ll sum; bool tag; }t[N << 2]; inline void addedge (int u, int v) { e[++tot] = (edge) {head[u], v}; head[u] = tot; } inline int count (ll x) { int ret = 0; while (x) x -= lowbit(x), ++ret; return ret; } inline void dfs (int u, int fa) { L[u] = ++tim; ti[tim] = u; edge(i, u) { if (v == fa) continue; dfs(v, u); } R[u] = tim; } inline void pushdown (int k) { if (t[k].tag) { t[k].tag = 0; t[ls].sum = t[rs].sum = t[k].sum; t[ls].tag = t[rs].tag = 1; } } inline void build (int k, int l, int r) { if (l == r) {t[k].sum = 1ll << a[ti[l]]; return;} int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); t[k].sum = t[ls].sum | t[rs].sum; } inline void modify (int k, int l, int r, int x, int y) { if (x <= l && r <= y) {t[k].sum = 1ll << val; t[k].tag = 1; return;} pushdown(k); int mid = l + r >> 1; if (x <= mid) modify(ls, l, mid, x, y); if (mid < y) modify(rs, mid + 1, r, x, y); t[k].sum = t[ls].sum | t[rs].sum; } inline ll query (int k, int l, int r, int x, int y) { if (x <= l && r <= y) {return t[k].sum;} pushdown(k); int mid = l + r >> 1; if (y <= mid) return query(ls, l, mid, x, y); if (x > mid) return query(rs, mid + 1, r, x, y); return query(ls, l, mid, x, y) | query(rs, mid + 1, r, x, y); } int main () { scanf("%d %d", &n, &m); fo (i, 1, n) scanf("%d", &a[i]); fo (i, 2, n) { scanf("%d %d", &x, &y); addedge(x, y); addedge(y, x); } dfs(1, 0); build(1, 1, n); fo (I, 1, m) { scanf("%d", &opt); if (opt == 2) { scanf("%d", &x); ll ans = query(1, 1, n, L[x], R[x]); // printf("%d \n", I); printf("%d\n", count(ans)); } else { scanf("%d %d", &x, &val); modify(1, 1, n, L[x], R[x]); } } return 0; } ```