뿌리 찾기 > 문제은행



실전대비 Level8

1731 : 뿌리 찾기

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 10 회    시도횟수: 33 회   



트리에 대한 정보가 주어지고 임의의 두 노드 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



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.