시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 256 MB5701306815.281%

문제

태초에 세계는 \(n\)개의 도시와 이들 사이를 잇는 \(n - 1\)개의 도로로 이루어져 있었다. 각 도시에는 0 이상 \(n-1\) 이하의 정수 번호가 붙어 있었다. 각 도로는 양방향으로 통행 가능하며, 양 끝에 서로 다른 두 개의 도시를 연결하고 있었다. 태초에 세계는 임의의 도시에서 출발하여 다른 모든 도시로 한 개 이상의 도로를 통하여 걸어갈 수 있었다. 

지혜를 갖춘 인간들은 어느새 찬란한 문명을 가지게 되었으나, 도시 사이에 새로운 도로를 놓는 일만큼은 어떻게 해도 해낼 수가 없었다.

이를 지켜보던 조물주는 해마다 두 도시를 잇는 도로를 하나씩 추가하기 시작했는데, 동시에 인간들이 새로운 도로를 사용하기에 합당한 지적 능력을 갖추고 있는지가 궁금해졌다. 그래서 인간들에게 아래와 같은 퍼즐 문제를 제시하였다.

매번 도로가 추가되고 나면 모든 도로 중 일부를 선택하여 모든 도시가 서로 직간접적으로 연결되어 있도록 하며,

이때 선택된 도로들의 길이의 합을 최소로 하는 도로의 부분집합을 알아내기.

조물주에게 문제를 받은 인간들은, 이 문제를 해결하여 조물주에게 자신들이 도로를 사용하기에 합당한 존재라는 것을 보여주기로 하였다. 만약 문제를 해결하지 못한다면, 인간들에게 실망한 조물주가 어떤 일을 일으킬지 아무도 알 수 없다. 당신은 인간계 대표로서, 조물주가 내린 시련을 이겨내야만 한다!

입력

첫 줄에는 테스트 케이스의 수 \(T\)가 정수로 주어진다. 이어서 매 테스트 케이스의 첫 줄에는 도시의 수 \(n\)과 도로가 건설된 횟수 \(m\)이 공백으로 구분되어 주어진다. 다음 \(n - 1\)줄에 태초의 세계에 대한 정보가 주어진다. 이 중 \(i\) (\(1 \leq i \leq n - 1\))번째 줄에는 정수 \(u_i, c_i\) (\(0 \leq u_i < i, 0 \leq c_i \leq 10,000,000\))가 공백으로 구분되어 주어지는데, 이는 \(i\)번 도시와 \(u_i\)번 도시가 길이가 \(c_i\)인 도로로 연결되어 있다는 뜻이다. 이어서 \(m\)개의 줄에 조물주가 새로이 놓은 도로에 대한 정보가 주어진다. 이 중 \(j\) (\(1 \leq j \leq m\))번째 줄에는 정수 \(u_j, v_j, c_j\) (\(0 \leq u_j, v_j < n, 0 \leq c_j \leq 10,000,000\))가 공백으로 구분되어 주어지는데, 이는 조물주가 \(j\)번째로 놓은 도로는, \(u_j\)번 도시와 \(v_j\)번 도시 사이를 연결하며, 길이가 \(c_i\)라는 것을 의미한다.

이 문제는 두 개의 부분문제로 이루어져 있다.

1번 문제의 입력은 \(1 \leq n, m \leq 2,000\)을 만족하며 해결하면 20점을 얻을 수 있다.

2번 문제의 입력은 \(1 \leq n, m \leq 100,000\)을 만족하며 해결하면 80점을 얻을 수 있다.

출력

각 테스트 케이스마다 단 하나의 줄을 출력한다. 이 줄에는 매번 새 도로를 놓았을 때 문제에 대한 답을 모두 XOR한 값을 출력한다.

예제 입력 1

1
3 3
0 5
1 3
0 2 4
0 1 2
0 0 2

예제 출력 1

7

출처

Contest > Coder's High > Coder's High 2015 Side Contest C2번

  • 문제를 만든 사람: tae

비슷한 문제