問題
수의사 동욱이는 동물병원을 새로 차렸다. 동욱이의 동물병원에는 N개의 병실이 있으며 각각 1 이상 N 이하의 서로 다른 정수 번호가 붙어있다. 일부 병실에는 통로가 있는데, 통로는 서로 다른 두 병실을 양방향으로 연결하며 총 N-1개 있다. 어떤 두 병실 사이를 선택하더라도 통로를 이용해서 이동 가능하다.
동욱이의 동물병원에서 반려동물이 수시로 입원 또는 퇴원한다. 입원하는 반려동물은 개 또는 고양이이며, 하나의 병실에는 오직 한 마리의 동물만 입원할 수 있다. 휴식 시간에 입원한 동물들이 통로를 이용해 움직일 수 있으나, 체계적인 관리를 위해 동욱이는 새로운 동물이 입원하거나 기존 동물이 퇴원하기 직전에는 입원한 동물들을 원래 위치로 옮긴다.
휴식시간에 고양이와 개가 서로 만난다면 돌발상황이 발생할 수 있기 때문에, 동욱이는 일부 통로를 폐쇄하여 개와 고양이가 서로 만나지 못하도록 하려고 한다. 통로 폐쇄는 꽤 번거로운 일이라서, 동욱이는 통로를 가능한 한 적게 폐쇄하여 목적을 달성하려고 한다.
앞으로 있을 Q개의 입/퇴원 일정이 주어지면 각 일정 이후 폐쇄하는 통로의 최소 수를 구하는 프로그램을 작성하여라.
入力
첫 번째 줄에는 병실의 수 N이 주어진다.
두 번째 줄부터 N-1개의 줄에는
N+1번째 줄에는 일정의 수 Q가 주어진다.
N+2번째 줄부터 Q개의 줄에는 입/퇴원 일정이 아래 세 가지 형식 중 하나의 방법으로 주어진다.
1 v: v번 병실에 개가 입원한다.2 v: v번 병실에 고양이가 입원한다.3 v: v번 병실에 있던 동물이 퇴원한다.
잘못된 일정(이미 동물이 있는 병실에 새로 입원하거나, 동물이 없는 병실에서 퇴원하거나)은 주어지지 않는다.
出力
Q개의 줄에 걸쳐 정답을 출력한다.
i번째 줄에는 앞선 i개의 일정 이후 휴식시간에 폐쇄해야 할 통로의 최소 개수를 출력한다.
部分問題
| 番号 | 点数 | 条件 |
|---|---|---|
| #1 | 8点 | 1 ≤ N ≤ 15 1 ≤ Q ≤ 100 |
| #2 | 30点 | 1 ≤ N ≤ 1 000 1 ≤ Q ≤ 1 000 |
| #3 | 62点 | 1 ≤ N ≤ 100 000 1 ≤ Q ≤ 100 000 |
例題 #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
병실이 5개 있고, 1번-2번 병실 사이, 2번-3번 병실 사이, 2번-4번 병실 사이, 그리고 4번-5번 병실 사이를 연결하는 통로가 4개 있는 경우를 생각해보자.
2번째 일정 이후, 3번 병실에 개가 있고 5번 병실에 고양이가 있다. 2번-4번 사이의 통로를 막으면 고양이와 개가 만나는 것을 막을 수 있으므로, 정답은 1이다.
4번째 일정 이후 2번 병실에 새로운 개가, 1번 병실에 새로운 고양이가 입원한다. 그러면 2번-4번 사이의 통로, 그리고 1번-2번 사이의 통로를 막아야 고양이와 개가 만나는 것을 막을 수 있고, 정답은 2이다.
5번째 일정 이후 2번 병실에 있던 개가 퇴원한다. 그러면 2번-3번 사이의 통로만 막으면 되므로 정답이 1이 된다.
ログインしないとコードを書けません。