21730번 - 불순 분자 만들기

문제

화학과 대학원생 탐레프는 $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번 쿼리에 대해, 각 쿼리의 결과를 한 줄에 하나씩 출력한다.

제한

• 1ドル \le n, m, q \le 100,000円$
• 입력으로 주어지는 트리는 올바른 트리이다.
• 1ドル \le s_{i}, e_{i} \le n$
• 2ドル$번 쿼리가 하나 이상 주어진다.

힌트