시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 (하단 참고)1024 MB36201753.125%

문제

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

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

예제 입력 1

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

예제 출력 1

3
4
2
3

노트

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

출처

University > 인하대학교 > 2021 인하대학교 프로그래밍 경진대회(IUPC) L번

시간 제한

  • Java 8: 3 초
  • Java 8 (OpenJDK): 3 초
  • Java 11: 3 초
  • Kotlin (JVM): 3 초
  • Java 15: 3 초