| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 257 | 67 | 50 | 21.552% |
\(N\)개의 정점과 \(N-1\)개의 양방향 간선으로 구성된 트리가 주어진다. 정점 번호는 \(0\)부터 \(N-1\)까지이고 \(0\)번 정점이 루트이다. 주어진 트리에 대한 다음과 같은 쿼리를 $Q$번 수행하자.
첫 번째 줄에 정점의 수 \(N\)이 입력된다. \((2\le N \le 100,000円)\)
다음 \(N-1\)개 줄에 부모 정점 번호 \(p\)와 자식 정점 번호 \(c\)가 공백으로 구분되어 입력된다. 입력으로 주어지는 그래프는 트리이다. \((0\le p\le N-1, 0 \le c \le N-1, p ≠ c)\)
다음 줄에 쿼리의 수 \(Q\)가 입력된다. \((1\le Q \le 100,000円)\)
다음 \(Q\)개의 줄에 \(k, v_1, v_2, v_3, ..., v_k\)가 공백으로 구분되어 입력된다. \(k\)의 총합은 \(10^6\) 이하이다. \((1 \le k \le N\), \(0 \le v_i \le N-1(1 \le i \le k)\), \(v_i ≠ v_j(1 \le i < j \le k))\)
입력으로 주어지는 모든 수는 정수이다.
쿼리가 주어질 때마다 쿼리의 답을 한 줄에 하나씩 출력한다.
7 0 1 0 2 1 3 1 4 2 5 2 6 5 1 1 2 0 1 2 1 2 3 2 3 4 7 0 1 2 3 4 5 6
1 1 2 1 3 3 5 10 7 21
첫 번째 쿼리는 \(1\)번 정점을 포함하는 정점의 수가 가장 작은 연결 컴포넌트 \(C\)를 찾으면 된다. 연결 컴포넌트 \(C\)에 포함된 정점 집합은 \(\{1\}\)이다.
두 번째 쿼리는 \(0\)번 정점, \(1\)번 정점을 모두 포함하는 정점의 수가 가장 작은 연결 컴포넌트 \(C\)를 찾으면 된다. 연결 컴포넌트 \(C\)에 포함된 정점 집합은 \(\{0,\ 1\}\)이다.
세 번째 쿼리는 \(1\)번 정점, \(2\)번 정점을 모두 포함하는 정점의 수가 가장 작은 연결 컴포넌트 \(C\)를 찾으면 된다. 연결 컴포넌트 \(C\)에 포함된 정점 집합은 \(\{0,\ 1,\ 2\}\)이다.
네 번째 쿼리는 \(2\)번 정점, \(3\)번 정점, \(4\)번 정점을 모두 포함하는 정점의 수가 가장 작은 연결 컴포넌트 \(C\)를 찾으면 된다. 연결 컴포넌트 \(C\)에 포함된 정점 집합은 \(\{0,\ 1,\ 2,\ 3,\ 4\}\)이다.
다섯 번째 쿼리는 모든 정점을 포함하는 정점의 수가 가장 작은 연결 컴포넌트 \(C\)를 찾으면 된다. 연결 컴포넌트 \(C\)에 포함된 정점 집합은 \(\{0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6\}\)이다.
School > 단국대학교부속소프트웨어고등학교 > 단대소프트고 2023 알고리즘 대회 F번