23091번 - Calculate! 3

도현이는 인경호에서 즐겁게 헤엄치는 오리, 인덕이를 바라보다가 흥미로운 사실을 발견했다. 그것은 인경호 수면 위에서 인덕이가 멈추는 지점을 정점으로, 인덕이의 동선을 간선으로 나타내면 놀랍게도 트리가 그려진다는 사실이다!

이 사실에 매우 감명한 도현이는 인덕이가 그리는 트리를 노트에 옮겨 그린 다음, 인덕이가 트리의 각 간선을 헤엄칠 때 날개짓하는 횟수를 세어 해당 간선의 가중치로 적어 넣었다. 그리고 문득 인덕이가 이 트리로 뭔가 메시지를 보내는 것 같다고 생각한 도현이는, 이 트리에서 얻을 수 있는 모든 서로 다른 경로를 기록했다. 그리고 각 경로에 포함된 간선들의 가중치를 모두 XOR 연산하여 계산 결과가 같은 경로가 몇 개씩 있는지 세기 시작했다.

그런데 XOR 연산하기에 몰두한 도현이를 보고 동우의 장난기가 발동해버렸다. 동우는 도현이의 사각을 노려 간선의 가중치를 조금씩 바꾸기 시작했다.

• 동우: (이 간선 가중치를 바꿔볼까 ㅋㅋ)
• 도현: 어...? 계산 결과가 30인 경로는 분명 7개였는데... 계산 실수했나?

우둔한 도현이는 가중치가 바뀌었다는 사실도 모르고 XOR 연산에 몰두했다.

동우는 도현이가 XOR 연산을 잘 계산하고 있는 것인지 궁금했다. 하지만 XOR 연산을 할 줄 모르는 동우는 이 상황을 쿼리로 주면 결과를 알려주는 프로그램이 있으면 좋겠다고 생각했다.

이 프로그램을 구현해보자.

첫째 줄에 두 개의 정수 \(N\), \(M\)이 주어진다. \(N\)은 트리의 정점 개수, \(M\)은 쿼리의 개수이다.

다음 \(N\)-1개의 줄에는 트리에 존재하는 간선이 "\(a\) \(b\) \(c\)"의 형태로 주어진다. 이는 초기 트리의 \(a\)번 정점과 \(b\)번 정점 사이의 가중치가 \(c\)임을 나타낸다.

다음 \(M\)개의 줄에는 한 줄에 하나씩 쿼리가 주어진다. 쿼리의 입력은 다음 형태를 따른다.

• 1 \(a\) \(b\) \(c\) : 정점 \(a\), \(b\)를 연결하는 간선의 가중치를 \(c\)로 바꾼다. \(a\)와 \(b\)를 연결하는 간선이 존재함이 보장된다.
• 2 \(c\) : XOR 연산 결과가 \(c\)인 서로 다른 경로의 개수를 출력한다.

2번 쿼리가 주어질 때마다 경로 XOR 합이 \(c\)인 경로의 개수를 한 줄에 출력한다.

경로는 적어도 하나의 간선을 포함해야 하며, 역방향인 두 경로는 같은 경로로 취급한다. 즉, 정점 A에서 출발해 정점 B로 도착하는 경로와 정점 B에서 출발해 정점 A로 도착하는 두 경로는 같은 경로이므로, 1번만 센다.

• 3 ≤ \(N\) ≤ 100,000
• 1 ≤ \(M\) ≤ 200,000
• 1 ≤ \(a\), \(b\) ≤ \(N\), \(a ≠ b\) 
• 1 ≤ \(c\) ≤ 30

XOR 연산은 배타적 논리합의 정의를 따른다.