문제
정올 아파트는 정점 N개와 N-1개의 복도로 구성된 트리 모양의 집들로 구성되어 있다. 각 집에는 아무도 살고 있지 않거나, 민트초코를 좋아하는 사람이 살고 있거나, 민트초코를 싫어하는 사람이 살고 있다.
아파트 경비원인 당신은 매일같이 민트초코를 좋아하는 사람들과 싫어하는 사람들 사이에서 발생하는 싸움을 말리느라 지쳐, 최소 개수의 복도를 막아 민트초코를 좋아하는 사람과 싫어하는 사람이 막히지 않은 도로만을 이용하여 만날 수 없도록 하고자 한다.
또한, Q일동안 매일같이 이 아파트에는
1. 빈 집에 민트초코를 좋아하는 사람이 들어오거나,
2. 빈 집에 민트초코를 싫어하는 사람이 들어오거나,
3. 사람이 있는 집에 살고 있던 사람이 떠나는,
3가지 종류의 사건이 발생한다. 당신은 각 사건 이후 막아야 하는 복도의 개수의 최솟값을 구해야 한다.
입력
첫번째 줄에 정점의 개수 N이 주어진다.
N-1개의 줄에 두 정수 u, v가 공백 하나를 사이에 두고 주어진다. i+1번째 줄의 입력은 i번째 복도는 Ui, Vi를 잇는다는 것을 의미한다. (Ui!=Vi, 전체 그래프는 연결된 트리 구조를 이룬다.)
세 번째 줄에 사건의 개수 Q가 주어진다.
Q개의 줄에 두 정수 T, v가 공백 하나를 사이에 두고 주어진다. T는 사건의 종류로 위의 1, 2, 3번 사건에 해당하며 v는 사건이 발생하는 집을 의미한다.
출력
각 사건이 발생한 이후의 답을 한 줄에 하나씩 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 8점 | 1<=N<=15 1<=Q<=100 |
| #2 | 30점 | 1<=N<=1000 1<=Q<=1000 |
| #3 | 62점 | 1<=N<=100000 1<=Q<=100000 |
예제 #1
3
1 2
2 3
4
1 1
1 3
2 2
3 2
0
0
2
0
예제 #2
5
1 2
2 3
2 4
4 5
5
1 3
2 5
1 2
2 1
3 2
0
1
1
2
1
로그인해야 코드를 작성할 수 있어요.