트리와 XOR 쿼리

1번 노드를 루트로 하고 간선에 가중치가 있는 트리가 주어진다. 모든 노드의 번호는 $1, 2, \cdots, N$ 이다. 두 노드 $x$, $y$ 에 대하여 $x$에서 $y$로 가는 단순 경로 위의 모든 가중치를 xor한 값을 $d(x,y)$로 정의하자. $x=y$ 이면 $d(x,y)=0$ 이다.

다음 두 쿼리를 수행하는 프로그램을 작성하시오.

1 $x$ $v$ : $x$번 노드에서 $x$번 노드의 부모로 가는 간선의 가중치를 $v$ 로 바꾼다.

2 $x$ $y$ : $x$의 서브 트리에 속한 임의의 정점 $a$와 $y$의 서브 트리에 속한 임의의 정점 $b$에 대하여, 모든 $d(a,b)$ 값의 총합을 출력한다.

첫째 줄에 트리의 노드 개수를 나타내는 정수 $N$이 주어진다. $(2 \leq N \leq 100,000)$

둘째 줄부터 $N-1$개의 줄에는 간선에 대한 정보를 나타내는 정수 $x, y, d$ 가 주어진다. 이는 최초의 트리에서 $x$번 노드와 $y$번 노드를 잇는 간선의 가중치가 $d$임을 나타낸다. $(1 \leq x, y \leq N$, $x \neq y$, $0 \leq d \leq 10^6)$

다음 줄에는 쿼리의 개수를 나타내는 정수 $Q$가 주어진다. $(1 \leq Q \leq 100,000)$

다음 $Q$개의 줄에는 한 줄에 하나씩 다음과 같은 형식 중 하나로 쿼리가 주어진다. 주어지는 모든 입력은 정수이다.

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

2번 쿼리는 한 번 이상 주어지며, $x$와 $y$가 같을 수 있음에 유의하라.

각각의 2번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

xor 연산은 아래 링크에서 확인하자.

링크