동기화 Batch 컴파일 명령
| 시간 제한 | 메모리 제한 | 제출 횟수 | 통과한 사람 수 | 비율 |
|---|---|---|---|---|
| 8000 ms | 256 MiB | 885 | 284 | 32.09% |
JOI Co., Ltd.는 전 세계에 무려 $N$대의 서버를 두고 있습니다. 각 서버에는 중요한 정보의 일부가 저장되어 있고, 서로 다른 서버에는 서로 다른 정보가 저장되어 있습니다. JOI Co., Ltd.는 서버들끼리 정보를 공유하기 위해 서버들 사이에 정보를 양방향으로 교환할 수 있는 회선을 설치하고 있습니다. 정보들은 회선을 통해 여러 서버를 거쳐갈 수 있습니다.
각 서버는 고성능 동기화 시스템을 갖추고 있습니다. 두 서버가 서로 정보를 교환할 수 있는 상태이고, 서로 다른 정보를 가지고 있다면, 두 서버는 자동으로 서로의 정보를 공유합니다. 두 서버 A와 B 사이에 동기화가 이루어졌다면, A와 B가 가지고 있는 정보는 동기화 이전 A가 가지고 있던 정보와 B가 가지고 있던 정보의 합집합이 됩니다.
돈을 아끼기 위해, 회선은 $N-1$개만 설치됩니다. $N-1$개의 회선이 설치되고 나면, 임의의 두 서버 사이에 정보를 전달하는 경로는 유일할 것이고, 이 경로 상에서 거쳐 간 서버를 또 거쳐갈 일은 없습니다.
초기 (시간 0)에는 아무 회선도 지어지지 않은 상태입니다. 가끔씩 회선이 혹독한 환경 (사막, 바다 속, ..)에 설치되는 일도 있기 때문에, 회선이 이용 불가능할 때도 있습니다. 회선 하나가 작동하지 않으면, 복구될 때까지 정보들이 이 회선을 거쳐갈 수 없습니다.
시간 $j$ ($1 \le j \le M$)에는 반드시 회선 하나의 작동 여부가 바뀐다는 것이 알려져 있습니다. 우리는 시간 $M+1$에 몇 개의 서버에 들어 있는 서로 다른 정보의 개수를 구하고 싶습니다.
문제
지어질 회선의 정보와 그 상태가 주어질 때, 임의의 서버에 저장된 서로 다른 정보의 수를 구하는 프로그램을 작성하세요.
입력
표준 입출력에서 아래 정보를 읽으세요:
첫째 줄에 세 정수 $N$, $M$, $Q$가 공백 하나를 사이로 두고 주어집니다. 이는 서버가 $N$개 있고, 회선의 작동 여부는 $M$번 바뀌며, 저장된 서로 다른 정보의 수를 구해야 할 서버는 $Q$개임을 말합니다.
$N-1$개 줄이 더 주어집니다. 이 중 $i$ ($1 \le i \le N-1$)번째 줄에 두 정수 $X_i$와 $Y_i$가 공백을 사이로 두고 주어집니다. 이는 $i$번 회선은 (지어진다면) $X_i$번 서버와 $Y_i$번 서버를 연결한다는 것을 말합니다.
$M$개의 줄이 더 주어집니다. 이 중 $j$ ($1 \le j \le M$)번째 줄에 하나의 정수 $D_j$가 주어집니다. 이는 $D_j$번 회선의 작동 여부가 시간 $j$에 바뀐다는 것을 말합니다. 다시 말하자면 아래와 같습니다.
(1) 만약 시간 $j$가 되기 직전에 $D_j$번 회선이 아직 건설되지 않았다면 새로 건설됩니다.
(2) 만약 시간 $j$가 되기 직전에 $D_j$번 회선이 작동한다면, 시간 $j$에 $D_j$번 회선이 작동하지 않기 시작합니다.
(3) 만약 시간 $j$가 되기 직전에 $D_j$번 회선이 작동하지 않는다면, 시간 $j$에 $D_j$번 회선이 작동하기 시작합니다.
(4) 회선의 상태를 바꾸는 데 필요한 모든 작업 (회선 건설, 동기화 작업 등) 은 시간 $j+1$이 되기 전에 끝납니다.$Q$개의 줄이 더 주어집니다. 이 중 $k$ ($1 \le k \le Q$)번째 줄에 하나의 정수 $C_k$가 주어집니다. 이는 마지막에 $C_k$번 서버에 저장된 서로 다른 정보의 수를 구해야 함을 의미합니다.
출력
표준 출력에 $Q$개의 줄을 출력하세요. 출력의 $k$ ($1 \le k \le Q$)번째 줄은 마지막 (시간 $M+1$)에 $C_k$번 서버에 저장된 서로 다른 정보의 수를 포함해야 합니다.
입력 조건
모든 입력 데이터는 아래 조건을 만족합니다.
- $2 \le N \le 200 000.$
- $1 \le M \le 100 000.$
- $1 \le Q \le N.$
- $1 \le X_i \le N, 1 \le Y_i \le N, X_i \neq Y_i$ ($1 \le i \le N-1$)
- $1 \le D_j \le N-1.$ ($1 \le j \le M$)
- $1 \le C_k \le N.$ ($1 \le k \le Q$)
- $C_k$의 값은 서로 다릅니다.
- 만약 모든 회선이 건설되었다면, 임의의 두 서버는 회선을 따라 연결되어 있음이 보장되어 있습니다.
서브태스크
서브태스크 1-2 (10점/20점)
- $Q = 1$임이 보장되어 있습니다.
서브태스크 3-4 (10점/20점)
- $X_i = i$, $Y_i = i+1$ ($1 \le i \le N-1$)임이 보장되어 있습니다.
서브태스크 5 (40점)
별다른 제약 조건이 없습니다.
입력과 출력의 예
| 입력 | 출력 |
|---|---|
| 5 6 3 1 2 1 3 2 4 2 5 1 2 1 4 4 3 1 4 5 |
3 5 4 |
초기에 $i$번 서버가 $i$번 정보를 저장하고 있다고 가정해 봅시다. ($1 \le i \le N$)
- 시간 1: 1번 회선이 설치되어 1번과 2번 서버가 연결됩니다. 그러면 두 서버 모두 1번과 2번 정보를 가지게 됩니다.
- 시간 2: 2번 회선이 설치되어 1번과 3번 서버가 연결됩니다. 그러면 1번, 2번, 3번 서버 모두 연결된 상태가 되어, 이 세 서버 모두 1번, 2번, 3번 정보를 가지게 됩니다.
- 시간 3: 이전에 1번 회선이 작동했기 때문에 지금부터 작동하지 않습니다. (다시 작동할 수도 있습니다.)
- 시간 4: 4번 회선이 설치되어 2번과 5번 서버가 연결됩니다. 그러면 2번과 5번 서버가 1번, 2번, 3번, 5번 정보를 가지게 됩니다. 1번 회선이 작동하지 않기 때문에 1번과 2번 서버는 동기화할 수 없음을 참고하세요.
- 시간 5: 4번 회선이 작동하지 않습니다. (다시 작동할 수도 있습니다.)
- 시간 6: 3번 회선이 설치되어 2번과 4번 서버가 연결됩니다. 그러면 2번과 4번 서버가 1번, 2번, 3번, 4번, 5번 정보를 가지게 됩니다.
위에서 말했듯이, 마지막에는 1번, 4번, 5번 서버가 각각 3개, 5개, 4개의 서로 다른 정보를 가지고 있습니다.