洛谷树

题目描述

给定一棵有 $n$ 个节点的带权树。对一条树上路径，把它看成按顺序排列的边权序列。该路径的子路径是这段序列的任意连续子段，也允许只包含一个节点，此时没有边且异或值为 $0$。

支持两种操作：

• 1 u v：求 $u$ 到 $v$ 的路径上所有子路径的边权异或值之和；
• 2 u v w：把边 $(u,v)$ 的权值修改为 $w$，保证该边存在。

输入格式

第一行两个整数 $n,q$。接下来 $n-1$ 行，每行三个整数 $u,v,w$ 描述一条边。接下来 $q$ 行描述操作。

输出格式

对每个类型 1 操作输出一行一个整数。

样例输入 1

5 3
1 2 3
2 3 3
2 4 6
4 5 1
1 3 4
2 2 4 7
1 3 5

样例输出 1

14
26

数据范围

$1\le n,q\le3\times10^4$，$0\le w\le1023$，输入的边构成一棵树。