조상인가요
골드 II의견: 0
정점 \(1\)번을 뿌리로 하는 트리가 주어진다.
정점 \(u\)가 정점 \(v\)의 조상이라는 것은, 뿌리에서 \(v\)로 가는 경로 위에 \(u\)가 있다는 뜻이다. 특히 정점은 자기 자신의 조상으로 친다.
다음 두 종류의 쿼리를 처리하여라.
1 u v— \(u\)가 \(v\)의 조상이면 \(1\)을, 아니면 \(0\)을 출력한다.2 v— \(v\)를 뿌리로 하는 서브트리에 속한 정점의 개수를 출력한다.
\(1 \le n \le 100\,000\), \(1 \le q \le 100\,000\), \(1 \le u, v \le n\).
첫째 줄에 정점의 개수 \(n\)이 주어진다. 다음 \(n-1\)개의 줄에 트리의 간선 \(a\ b\)가 주어진다 — 정점 \(a\)와 \(b\)가 직접 연결되어 있다는 뜻이다. 그다음 줄에 쿼리의 개수 \(q\)가 주어지고, 이후 \(q\)개의 줄에 위 형식의 쿼리가 주어진다.
각 쿼리마다 한 줄에 답(조상 여부 또는 서브트리 크기)을 출력한다.
6
1 2
1 3
2 4
2 5
3 6
6
1 1 5
1 2 6
1 5 4
2 2
2 3
2 1
1
0
0
3
2
6
\(1\)번은 모든 정점의 조상이므로 1 1 5는 \(1\)이다. \(2\)번은 \(6\)번의 조상이 아니므로 1 2 6은 \(0\)이고, \(5\)번은 \(4\)번의 조상이 아니므로 1 5 4도 \(0\)이다. \(2\)번의 서브트리는 \(\{2,4,5\}\)로 크기 \(3\), \(3\)번은 \(\{3,6\}\)으로 \(2\), \(1\)번은 전체 \(6\)이다.
1
2
1 1 1
2 1
1
1
정점이 하나뿐이면 자기 자신은 자기 자신의 조상이며 (조상 관계는 자기 자신을 포함한다) 서브트리 크기는 \(1\)이다.
골드 I막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
조상인가요
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
조상인가요