You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

CaiZi 讨厌三角形，但是他喜欢树。

2024.8.15 Update：增加了一组 hack 数据。

题目描述

给定一颗有 $n$ 个点的树，节点编号为 $1\sim n$，每个点有点权，开始时点 $i$ 的点权为 $a_i$。共有 $q$ 次操作。

1. 将点 $x$ 到点 $y$ 的简单路径上的点的点权异或 $k$。
2. 判断能否在点 $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$。