Tree and XOR Queries

A tree is given, rooted at node 1, with weights on its edges. Every node is numbered $1, 2, \cdots, N$. For two nodes $x$ and $y$, let $d(x,y)$ be the xor of all weights on the simple path from $x$ to $y$. If $x=y$, then $d(x,y)=0$.

Write a program that handles the following two queries.

1 $x$ $v$ : change the weight of the edge from node $x$ to the parent of node $x$ to $v$.

2 $x$ $y$ : for any vertex $a$ in the subtree of $x$ and any vertex $b$ in the subtree of $y$, output the sum of all values $d(a,b)$.

The first line gives the integer $N$, the number of nodes in the tree. $(2 \leq N \leq 100,000)$

Each of the next $N-1$ lines gives three integers $x, y, d$ describing an edge. This means the edge connecting node $x$ and node $y$ in the initial tree has weight $d$. $(1 \leq x, y \leq N$, $x \neq y$, $0 \leq d \leq 10^6)$

The next line gives the integer $Q$, the number of queries. $(1 \leq Q \leq 100,000)$

The next $Q$ lines give one query per line in one of the following forms. All inputs are integers.

• 1 $x$ $v$ $(2 \leq x \leq N$, $0 \leq v \leq 10^6)$
• 2 $x$ $y$ $(1 \leq x, y \leq N)$

Query type 2 appears at least once, and $x$ and $y$ may be equal.

Print the result of each type 2 query in order, one per line.

See the link below for the xor operation.

Link