记录编号	267394	评测结果	AAAAAAAAAA
题目名称	[HNSDFZ]ZY的钻石树	最终得分	100
用户昵称	Link	是否通过	通过
代码语言	C++	运行时间	4.946 s
提交时间	2016-06-11 08:40:31	内存使用	25.20 MiB

/*
题目：
1.修改一个节点的颜色值
2.查询一颗子树中有多少种不同的颜色的值
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#pragma warning(disable:4996)
#define NMAX 320000
struct BLOCK {
	int l;
	int r;
};
vector<int> m[NMAX];
vector<int> son[NMAX];
bool v[NMAX];
int pos[NMAX];
int top[NMAX];
int siz[NMAX];
int dep[NMAX];
int p[NMAX];
int endpos[NMAX];
int ccc[NMAX];
int num = 0;
//
int color[NMAX];
int barr[NMAX];
BLOCK block[1200];
int cnt = 0;
int be[NMAX];
int last[NMAX];
int help[1000101];
int sqrtn;
//
int n, q;
bool cmp(const int &a, const int &b) {
	if (last[a] < last[b]) return true;
	else return false;
}
inline int read(){
	int x = 0;
	int f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x*f;
}
void dfs(int x) {
	siz[x] = 1;
	v[x] = true;
	int size = m[x].size();
	for (int i = 0; i <= size - 1; i++) {
		int to = m[x][i];
		if (!v[to]) {
			p[to] = x;
			dep[to] = dep[x] + 1;
			son[x].push_back(to);
			dfs(to);
			siz[x] += siz[to];
		}
	}
}
void divide(int x, int topx) {
	num++;
	pos[x] = num;
	top[x] = topx;
	int MaxSon = 0;
	int id = 0;
	int size = son[x].size();
	if (!size) {
		endpos[x] = pos[x];
		return;
	}
	for (int i = 0; i <= size - 1; i++) {
		if (MaxSon < siz[son[x][i]]) {
			MaxSon = siz[son[x][i]];
			id = i;
		}
	}
	divide(son[x][id], topx);
	for (int i = 0; i <= size - 1; i++) {
		if (i != id) {
			divide(son[x][i], son[x][i]);
		}
	}
	endpos[x] = num;
}
void rebulid(int x) {
	for (int i = block[x].l; i <= block[x].r; i++) {
		barr[i] = i;
	}
	sort(barr + block[x].l, barr + block[x].r + 1, cmp);
}
void change(int x, int val) {
	vector<int> blo;
	if (color[x] == val) return;
	int p = help[color[x]];
	int ord = 0;
	if (p == x) {
		help[color[x]] = last[x];
	}
	while (true) {
		if (p == x) {
			last[ord] = last[p];
			blo.push_back(ord);
			last[p] = 0;
			break;
		}
		ord = p;
		p = last[p];
	}
	last[0] = 0;
	ord = 0;
	color[x] = val;
	p = help[color[x]];
	if (p < x) {
		help[color[x]] = x;
	}
	while (true) {
		if (p < x) {
			last[x] = p;
			last[ord] = x;
			blo.push_back(ord);
			break;
		}
		ord = p;
		p = last[p];
	}
	last[0] = 0;
	rebulid(be[x]);
	int size = blo.size();
	for (int i = 0; i <= size - 1; i++)
		rebulid(be[blo[i]]);
}
int  query(int l, int r) {
	int ans = 0;
	if (l > r) swap(l, r);
	if (be[l] == be[r]) {
		for (int i = l; i <= r; i++) {
			if (last[i] < l) ans++;
		}
	}
	else {
		for (int i = l; i <= block[be[l]].r; i++) {
			if (last[i] < l) ans++;
		}
		for (int i = block[be[r]].l; i <= r; i++) {
			if (last[i] < l) ans++;
		}
		for (int i = be[l] + 1; i <= be[r] - 1; i++) {
			for (int j = block[i].l; j <= block[i].r; j++)
				if (last[barr[j]] < l) ans++;
				else break;
		}
	}
	return ans;
}
void GetBlock() {
	sqrtn = (int)sqrt(n);
	if (n%sqrtn) cnt = (n / sqrtn) + 1;
	else cnt = n / sqrtn;
	for (int i = 1; i <= cnt; i++) {
		block[i].l = block[i - 1].r + 1;
		block[i].r = block[i].l + sqrtn - 1;
	}
	block[cnt].r = n;
	for (int i = 1; i <= cnt; i++) {
		for (int j = block[i].l; j <= block[i].r; j++)
			be[j] = i;
	}
	for (int i = 1; i <= n; i++) {
		last[i] = help[color[i]];
		help[color[i]] = i;
	}
	for (int i = 1; i <= cnt; i++) {
		rebulid(i);
	}
}
void Init() {
	n = read();
	for (int i = 1; i <= n; i++) {
		ccc[i] = read();
	}
	for (int i = 1; i <= n - 1; i++) {
		int u = read();
		int v = read();
		m[u].push_back(v);
		m[v].push_back(u);
	}
	q = read();
	dfs(1);
	divide(1, 1);
	for (int i = 1; i <= n; i++) {
		color[pos[i]] = ccc[i];
	}
	GetBlock();
	
}
int main() {

	freopen("zytree.in", "r", stdin);
	freopen("zytree.out", "w", stdout);
	Init();
	for (int i = 1; i <= q; i++) {
		int k = read();
		if (k) {
			int x = read();
			printf("%d\n", query(pos[x], endpos[x]));
		}else {
			int x = read();
			int c = read();
			change(pos[x], c);
		}
	}
	
}