시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1536 MB | 118 | 21 | 20 | 25.641% |
화학과 대학원생 탐레프는 $n$개의 원자를 갖는 트리 모양의 분자를 만들었다. 그런데 몇개의 불순 전자들이 분자를 불순 분자로 만들기 위해 이리저리 돌아다니며 선전을 하고 있는 것이 발각되고 말았다. 탐레프는 불순 전자들을 저지하기 위해 $m$개의 전자 현미경을 놓아 전자들을 감시하려고 한다.
각 전자 현미경은 두 원자 사이의 유일한 최단경로 위에 있는 원자들을 감시할 수 있다. 특별히 $i$번 전자 현미경은 $s_{i}$번 원자와 $e_{i}$번 원자 사이의 경로에 있는 원자들을 감시할 수 있다. 최단 경로는 양 끝점을 포함한다.
불순 전자들은 두 원자 사이를 옮겨 다닐 때 최단 경로로 이동한다. 한 불순 전자가 이동할 때, 그 전자와 경로가 겹치는 현미경의 감시 실적이 $1$ 오른다. 현미경은 전자를 붙잡을 수는 없다는 것에 주의하자.
탐레프는 불순 전자들이 자주 이동하는 경로를 찾기 위해 수시로 전자 현미경의 실적들을 조회한다. 전자가 이동하거나 실적을 조회하는 쿼리 $q$개를 처리하는 프로그램을 작성하여 보자.
첫째 줄에 원자 개수 $n$, 전자 현미경의 수 $m$, 쿼리의 개수 $q$가 공백으로 구분되어 주어진다.
둘째 줄부터 $n-1$개의 줄에 걸쳐 분자 구조가 주어진다. $i+1$번째 줄에는 두 정수 $u_{i}, v_{i}$가 주어지며, 이는 $i$번째 결합선이 $u_{i}$번 원자와 $v_{i}$번 원자를 연결한다는 것을 의미한다.
$n+1$번째 줄부터 $m$개의 줄에 걸쳐 전자 현미경이 감시하는 경로의 양 끝 원자 번호가 주어진다. $n + i$번째 줄에는 $s_{i}, e_{i}$가 공백으로 구분되어 주어진다.
$n + m + 1$번째 줄부터 $q$개의 줄에 걸쳐 아래 두 종류의 쿼리가 주어진다.
1 x y
: 전자 하나가 $x$번 원자에서 $y$번 원자로 이동한다. ($1 \le x, y \le n$, $x \neq y$)2 k
: $k$번 전자 현미경의 현재 실적을 출력한다. ($1 \le k \le m$)모든 2번 쿼리에 대해, 각 쿼리의 결과를 한 줄에 하나씩 출력한다.
7 3 5 1 3 4 5 7 1 6 1 3 4 2 3 6 3 7 5 2 4 1 7 4 2 1 1 2 6 2 3 2 2
1 2 2
Contest > BOJ User Contest > IDTcup > 제 3회 IDTcup F번