Colorful Tree
시간 제한5초메모리 제한512 MB
트리 정점의 색을 점 갱신하면서, 특정 색을 가진 모든 정점을 포함하는 최소 연결 부분그래프의 간선 수를 묻는 질의에 답한다.
문제
정점에 색이 부여된 트리와 그 트리에 대한 명령의 나열이 주어진다. 명령은 갱신 연산 또는 질의이다. 각 갱신 연산은 트리 구조를 바꾸지 않으면서, 지정된 정점의 색을 바꾼다. 각 질의는 지정된 색을 가진 모든 정점을 포함하는 트리의 최소 연결 부분 그래프의 간선 수를 묻는다.
명령이 주어진 순서대로 수행된다고 가정할 때, 각 질의의 답을 구하시오.
입력
입력은 다음 형식의 단일 테스트 케이스로 주어진다.
n
a1 b1
.
.
.
an−1 bn−1
c1 . . . cn
m
command1
.
.
.
commandm
첫째 줄에는 트리의 정점 개수 n(2 ≤ n ≤ 100 000)이 주어진다. 정점은 1부터 n까지 번호가 매겨져 있다. 다음 n − 1개의 줄 각각에는 두 정수 ai(1 ≤ ai ≤ n), bi(1 ≤ bi ≤ n)가 주어지며, i번째 간선이 정점 ai와 bi를 연결한다는 뜻이다. 모든 정점이 연결되어 있으며, 즉 주어진 그래프는 트리임이 보장된다. 다음 줄에는 n개의 정수 c1부터 cn까지가 주어지며, cj(1 ≤ cj ≤ 100 000)는 정점 j의 초기 색이다. 다음 줄에는 명령의 개수 m(1 ≤ m ≤ 100 000)이 주어진다. 다음 m개의 줄 각각에는 다음 형식의 명령이 주어진다.
U xk yk
또는
Q yk
k번째 명령이 U로 시작하면, 정점 xk(1 ≤ xk ≤ n)의 색을 yk(1 ≤ yk ≤ 100 000)로 바꾸는 갱신 연산이다. k번째 명령이 Q로 시작하면, 색 yk(1 ≤ yk ≤ 100 000)인 모든 정점을 포함하는 트리의 최소 연결 부분 그래프의 간선 수를 묻는 질의이다.
출력
각 질의마다, 지정된 색의 모든 정점을 포함하는 트리의 최소 연결 부분 그래프의 간선 수를 출력한다. 트리에 지정된 색의 정점이 하나도 없다면, 대신 -1을 출력한다.