【codeforces 620E】【dfs】【線段樹 】【lazy】【子樹區間修改,區間求和】

https://codeforces.com/problemset/problem/620/E

【題意】

子樹區間修改,區間求和

【分析】先将樹形結構通過dfs序轉化為線性結構，子樹的操作轉化為線性區間上的操作，加個2進制ll存儲val,lazy标記更新

【代碼】

  好久沒寫線段樹了，嗚嗚嗚

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 6;
int c[maxn], pos[maxn];
vector<int>v[maxn];

//線段樹部分----------------------------------------------------------
struct node {
	int l, r;
	ll val;
	int lazy;
	int mid(void) {
		return l + r >> 1;
	}
}tr[maxn<<2];

void pushDown(int p) {
	if (tr[p].lazy) {
		tr[p << 1].lazy = tr[p << 1 | 1].lazy = tr[p].lazy;
		tr[p << 1 | 1].val = tr[p << 1].val = 1LL << tr[p].lazy;
		tr[p].lazy = 0;
	}
}

void build(int p, int l,int r) {
	tr[p].l = l;
	tr[p].r = r;
	tr[p].lazy = 0;
	tr[p].val = 0;
	if (l == r) {
		tr[p].val = 1LL << c[pos[l]];
		return;
	}
	int mid = tr[p].mid();
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	tr[p].val = tr[p << 1].val | tr[p << 1 | 1].val;
}

void update(int p, int l, int r, int L, int R, int x) {
	if (L <= tr[p].l&&tr[p].r <= R) {
		tr[p].lazy = x;
		tr[p].val = 1LL << x;
		return;
	}
	pushDown(p);
	int mid = tr[p].mid();
	if (L <= mid)update(p << 1, l, mid, L, R, x);
	if (R > mid)update(p << 1 | 1, mid + 1, r, L, R, x);
	tr[p].val = tr[p << 1].val | tr[p << 1 | 1].val;
}

ll query(int p, int l, int r, int L,int R) {
	if (L <= l && r <= R) {
		return tr[p].val;
	}
	pushDown(p);
	int mid = tr[p].mid();
	ll res = 0;
	if (L <= mid)res |= query(p << 1, l, mid, L, R);
	if (R > mid)res |= query(p << 1 | 1, mid + 1, r, L, R);
	tr[p].val = tr[p << 1].val | tr[p << 1 | 1].val;
	return res;
}

//dfs部分---------------------------------------------------------------
int dfsL[maxn], dfsR[maxn];
int tot = 0;
//獲得每個節點1->tot的編号
void dfs(int p, int f ) {//L,R表示一個子樹的範圍
	dfsL[p] = ++tot;
	pos[tot] = p;
	for (int q : v[p]) {
		if (q == f)continue;
		dfs(q, p);
	}
	dfsR[p] = tot;
}


int main() {
	int n, m;
	while (~scanf("%d%d", &n, &m)) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &c[i]);
			v[i].clear();
		}
		for (int i = 1; i < n; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1, 0);
		build(1, 1, n);
		while (m--) {
			int op;
			scanf("%d", &op);
			if (op == 1) {
				int v, x;
				scanf("%d%d", &v, &x);
				update(1, 1, n, dfsL[v], dfsR[v], x);
			}
			else {
				int v;
				scanf("%d", &v);
				ll ans = query(1, 1, n, dfsL[v], dfsR[v]);
				printf("%d\n", bitset<1000>(ans).count());
			}
		}
	}
}