| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB | 3634 | 935 | 642 | 25.866% |
1ドル$부터 $N$까지 $N$개의 정점으로 이루어진 트리가 있다. $i$번째 간선은 서로 다른 두 정점 $A_i,ドル $B_i$를 잇는다. (1ドル ≤ i ≤ N - 1$)
$N$개의 정점 중 몇 개를 골라, 그 고른 정점들을 $S = \{s_1, s_2, \dots , s_K\}$라고 하자. 또한, $s_i = v$를 만족하는 $i$ (1ドル ≤ i ≤ K$)가 존재할 때, 정점 $v$가 $S$에 속한다고 부르자.
$S$에 속하는 서로 다른 두 정점 $u,ドル $v$에 대하여, $S$에 속하는 정점만을 이용하여 트리 위에서 $u,ドル $v$ 사이를 오갈 수 있다면, “$u$와 $v$는 $S$ 위에서 연결되어 있다”고 하자.
예를 들어, 아래와 같은 트리를 생각하자. ($N = 7$)
만일, $K = 6,ドル $S = \{1, 2, 3, 4, 5, 6\}$라면, “1ドル$과 2ドル$”, “3ドル$과 5ドル$”, “4ドル$와 6ドル$”은 각각 서로 $S$ 위에서 연결되어 있다. 그러나, “1ドル$과 6ドル$”, “2ドル$와 7ドル$”은 각각 서로 $S$ 위에서 연결되어 있지 않다.
다음 조건을 모두 만족하는 정점쌍 $(u, v)$의 개수를 $S$의 연결 강도라고 하자.
고른 정점들 $S$가 주어질 때, $S$의 연결 강도를 계산하는 프로그램을 작성하라. 여러분은 이러한 질의 $Q$개에 대하여 모두 답해야 한다.
첫 번째 줄에 정수 $N$이 주어진다.
다음 ($N - 1$)개의 줄에 각 간선에 대한 정보가 주어진다. 이 중 $i$ (1ドル ≤ i ≤ N - 1$)번째 줄에는 두 정수 $A_i,ドル $B_i$가 주어진다.
다음 줄에 정수 $Q$가 주어진다.
다음 $Q$개의 줄에 각 질의에 대한 정보가 주어진다. 이 중 $i$ (1ドル ≤ i ≤ Q$)번째 줄은 $i$번째 질의를 나타내며, 정수 $K$와 $K$개의 정수 $s_1, \dots , s_K$가 차례대로 주어진다.
첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ (1ドル ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $N = 3$. |
| 2 | 10 | $N ≤ 50,ドル $Q ≤ 50$. |
| 3 | 11 | $N ≤ 2,500円,ドル $Q ≤ 2,500円$. |
| 4 | 13 | 각 질의에서, $K = 3$. |
| 5 | 63 | 추가 제약 조건 없음. |
7 1 2 1 3 1 5 2 7 4 6 4 7 6 1 1 2 1 2 4 1 2 3 4 5 1 2 4 6 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7
0 1 3 10 7 21
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 초등부 3번
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 중등부 2번
Olympiad > 한국정보올림피아드 > KOI 2022 2차대회 > 고등부 1번
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 4: KAIST+KOI Contest, Grand Prix of Korea B번