信息学奥赛题库- 树上数颜色

友情提示：380元/半年，儿童学编程，就上码丁实验室。

【题目描述】

送你一棵$n$个点的树，树根为$1$。一开始每个点上有一个$1sim 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
4 1 1 5 4
5 1
3 5
2 3
4 3
2 5 4
2 2 2
1 3 1 5
2 1 2
1 1 2 7

3
1

【数据规模和约定】

对于前20%的数据，$n,q≤5000$。

对于前40%的数据，$n,q≤50000$。

对于另20%的数据，没有修改操作。

对于另20%的数据，$t=0$。

对于100%的数据，$1≤n,q≤100000$。