24532번 - 트리와 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 연산은 아래 링크를 통해 확인하자.

링크