問題
트리에 대한 정보가 주어지고 임의의 두 노드 a와 b를 선택했을 때,
a가 b의 선조인지 아닌지 판별하는 프로그램을 작성하라.
여기서 a가 b의 선조라는 것은 b에서 a로 다다르는 최단 경로에 대해 거쳐 가는 노드 중
a보다 높은 레벨(여기서 레벨이 높다는 것은 루트에 가깝다는 이야기이다.)을 거치지 않을 수 있을 경우를 이야기 한다.
入力
입력은 트리에 대한 정보가 입력된다. 첫 번째 줄에는 노드의 개수를 의미하는 N(1≤N≤100,000)이 주어진다. 그 다음 줄부터 N개의 줄에는 자신과 연결되어 있는 자식 노드의 개수 M(0≤M＜N)이 주어지고, 빈 칸을 사이에 두고 연결된 자식 노드의 번호들이 입력된다. 1번 노드는 트리의 루트이며, M=0일 경우는 해당 노드는 단말노드이다.
그 다음 줄에는 선조를 알아보고자 하는 노드 쌍의 개수 K(1≤K≤100,000)이 입력되고 그 다음 줄부터 K개의 줄 마다 노드 쌍 a, b가 빈칸을 사이에 두고 입력된다(1≤a, b≤N).
出力
각각의 노드 쌍의 개수에 대해서 a가 b의 선조일 경우 Yes라 출력하고, 아닐 경우 No라고 출력한다.
例題
4
2 2 3
0
1 4
0
5
1 2
1 3
2 3
4 1
1 1
Yes
Yes
No
No
No
ログインしないとコードを書けません。