XOR Sum of All Subpath Edge Weights in a Tree

Consider a tree which is an undirected, connected graph without cycles, consisting of \( n \) nodes and \( n-1 \) edges. In a tree, the unique simple path between any two nodes is clearly the shortest path.

Now, we introduce the concept of a subpath. Suppose that the unique simple path between two nodes \( p_1 \) and \( p_n \) is \( P = \langle p_1, p_2, p_3, \ldots, p_n \rangle \). A subpath is defined as any contiguous segment \( P' = \langle p_i, p_{i+1}, \ldots, p_j \rangle \) where \( 1 \le i \le j \le n \). Note that the whole path is a subpath, and even a single node (which corresponds to a subpath with no edge) is considered a subpath.

Each edge in the tree is assigned a weight. For any two nodes \( u \) and \( v \), consider the unique path between them. For every subpath of this path, calculate the XOR (denoted by \( \oplus \)) of the weights of the edges that the subpath contains (for a subpath consisting of a single node, the XOR is \( 0 \) since there are no edges). The task is to compute the sum of all these XOR values.

Furthermore, you are required to support updating the weight of a specified edge.

Input/Output specifications and queries details are given below.

Note on \( \oplus \): If you are not familiar with the XOR operation, please search online for more details.

inputFormat

The first line contains two integers \( n \) and \( q \) representing the number of nodes in the tree and the number of queries respectively.

The following \( n-1 \) lines each contain three integers \( u\), \( v \), and \( w \) describing an edge between node \( u \) and node \( v \) with an initial weight \( w \). The edges are indexed from 1 to \( n-1 \) in the order they are given.

Each of the next \( q \) lines represents a query and is in one of the following two formats:

• Query: 1 u v where the task is to compute the sum of the XOR values of all subpaths on the unique path from node \( u \) to node \( v \).
• Update: 2 i w where you must update the weight of the \( i \)th edge to \( w \).

outputFormat

For each query of the first type, output a single line containing the required sum.

sample

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

6
14
19