「CZOI-R1」三角形与树

CaiZi 讨厌三角形，但是他喜欢树。 2024.8.15 Update：增加了一组 hack 数据。

给定一颗有 $n$ 个点的树，节点编号为 $1\sim n$，每个点有点权，开始时点 $i$ 的点权为 $a_i$。共有 $q$ 次操作。 1. 将点 $x$ 到点 $y$ 的简单路径上的点的点权**异或** $k$。 1. 判断能否在点 $x$ 到点 $y$ 的简单路径上选 $3$ 个**不同点**，并以这 $3$ 个点的点权为边长构成**三角形**。特别的，如果无法选出 $3$ 个点，也视为不能构成**三角形**。 点 $x$ 到点 $y$ 的简单路径：点 $x$ 到点 $y$ 不重复走过任何一条边的路径。其上的所有点为这条路径上所有的点，**包括**点 $x$ 和点 $y$。 **保证任何时刻不会有任何一个点的点权为 $0$。**

第一行输入 $2$ 个整数 $n,q$，分别表示这棵树点的个数、操作的个数。 第二行输入 $n$ 个整数 $a_i$，表示开始时点 $i$ 的点权。 接下来 $n-1$ 行，每行输入 $2$ 个整数 $u,v$，表示这棵树的一条边。 接下来 $q$ 行，每行先输入 $1$ 个整数 $s$，表示操作类型。 - 若 $s=1$，则再输入 $3$ 个整数 $u,v,w$，表示一次修改操作。 - 若 $s=2$，则再输入 $2$ 个整数 $u,v$，表示一次询问操作。

对于每次询问操作，若能满足条件输出 $1$，否则输出 $0$，无需空格或换行。

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

0110

**【样例解释】** 第 $1$ 次操作时简单路径上的点权少于 $3$ 个。 第 $2$ 次操作时简单路径上的点权分别为 $1,2,3,4$。 第 $3$ 次操作后点 $1\sim n$ 的点权分别为 $5,6,7,4,1$。 第 $4$ 次操作时简单路径上的点权分别为 $5,6,7$。 第 $5$ 次操作时简单路径上的点权分别为 $1,5,6$。 **【数据范围】** **本题采用捆绑测试**。 - Subtask #1（$8\text{ pts}$）：$n,q\le3\times10^3$。 - Subtask #2（$8\text{ pts}$）：保证这棵树是一朵菊花。 - Subtask #3（$20\text{ pts}$）：每次修改操作时 $x=y$。 - Subtask #4（$24\text{ pts}$）：保证这棵树是一条链。 - Subtask #5（$40\text{ pts}$）：无特殊性质。**依赖 Subtask #1 到 Subtask #4。** 对于 $100\%$ 的数据，$1\le u,v\le n\le10^5$，$1\le q\le10^5$，$s\in\{1,2\}$，$1\le a_i,w\le 2^{31}-1$。