树上数颜色

【题目描述】

送你一棵$n$个点的树，树根为$1$。一开始每个点上有一个$1\sim n$ 的颜色$c_i$，不同点颜色可以相同。 现在有 $q$ 次操作, 分为两种类型： $1\;u\;l\;r$：询问子树 $u$ 中有多少种在 $l$ 到 $r$ 之间的颜色至少出现了一次； $2\;u\;c$：将 $u$ 的颜色修改为 $c$。 部分测试点要求强制在线。

【输入】

第一行三个整数$n,q,t$，分别表示树的点数，操作的个数和是否强制在线。 $t=0$表示不强制在线，$t=1$表示强制在线。 接下来一行$n$个整数 $c_i$，表示每个点的初始颜色。 接下来$n-1$行，每行两个整数$u_i$;$v_i$表示一条$u_i$到$v_i$的边。 接下来$q$行，每行四个或三个整数，表示一个操作。 当$t=1$时，需要对第一个数以外的其他数异或上一次询问的答案$lastans$，初始时 $lastans=0$。

【输出】

对于每个询问输出一行一个整数，表示答案。

【输入样例】

5 5 0
5 5 2 5 5
5 1
2 5
4 2
3 5
1 2 2 3
2 5 1
1 1 1 5
2 3 2
1 3 1 5

【输出样例】

0
3
1

【提示】

5 5 1\n4 1 1 5 4\n5 1\n3 5\n2 3\n4 3\n2 5 4\n2 2 2\n1 3 1 5\n2 1 2\n1 1 2 7

3\n1

【数据规模和约定】

\n对于前20%的数据，$n,q≤5000$。\n对于前40%的数据，$n,q≤50000$。 \n对于另20%的数据，没有修改操作。\n对于另20%的数据，$t=0$。\n对于100%的数据，$1≤n,q≤100000$。");