3584번 - 가장 가까운 공통 조상 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB162178662651253.142%

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Ancestor)은 다음과 같이 정의됩니다.

  • 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

nca.png

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

예제 입력 1 

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

예제 출력 1 

4
3
W3sicHJvYmxlbV9pZCI6IjM1ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDFiNSBcdWM4NzBcdWMwYzEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjKHJvb3RlZCB0cmVlKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWQyYjhcdWI5YWMgXHVjMGMxXHVjNzU4IFx1YjQ1MCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWFkZjhcdWI0ZTRcdWM3NTggXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjZjVcdWQxYjUgXHVjODcwXHVjMGMxKE5lYXJlc3QgQ29tbW9uIEFuY2VzdG9yKVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWI0NTAgXHViMTc4XHViNGRjXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVhY2Y1XHVkMWI1IFx1Yzg3MFx1YzBjMVx1Yzc0MCwgXHViNDUwIFx1YjE3OFx1YjRkY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVjNzkwXHVjMTkwXHVjNzNjXHViODVjIFx1YWMwMFx1YzljMFx1YmE3NFx1YzExYyBcdWFlNGFcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YWU0YVx1Yzc0MChcdWM5ODkgXHViNDUwIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0KSBcdWIxNzhcdWI0ZGNcdWI5N2MgXHViOWQwXHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIm5jYS5wbmdcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC80ZjJlYWU1OC0zMWJmLTQ0NWYtYTdhMy02MjU1MDVlNzEwMmNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OjI3OHB4OyB3aWR0aDozMDRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0ICAxNVx1YzY0MCAxMVx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjNzkwXHVjMTkwXHVjNzNjXHViODVjIFx1YWMxNlx1YjI5NCBcdWIxNzhcdWI0ZGNcdWIyOTQgNFx1YzY0MCA4XHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYywgXHVhZGY4IFx1YzkxMSBcdWFlNGFcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YWU0YVx1Yzc0MCgxNVx1YzY0MCAxMVx1YzVkMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0KSBcdWIxNzhcdWI0ZGNcdWIyOTQgNCBcdWM3NzRcdWJiYzBcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjZjVcdWQxYjUgXHVjODcwXHVjMGMxXHVjNzQwIDRcdWFjMDAgXHViNDI5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4ZThcdWQyYjhcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1MCBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWFkZjggXHViNDUwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDFiNSBcdWM4NzBcdWMwYzFcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMxMzhcdWM2OTQ8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YjJlNFx1Yzc0YyBOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHVhYzA0XHVjMTIwIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1ZDU1YyBcdWFjMDRcdWMxMjAgXHViMmY5IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTAgQSBCIFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgQVx1YWMwMCBCXHVjNzU4IFx1YmQ4MFx1YmFhOFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3ODVcdWIyYzhcdWIyZTQuIChcdWIyZjlcdWM1ZjBcdWQ3ODggXHVjODE1XHVjODEwXHVjNzc0IE5cdWFjMWNcdWM3NzggXHVkMmI4XHViOWFjXHViMjk0IFx1ZDU2ZFx1YzBjMSBOLTFcdWFjMWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzlkMVx1YjJjOFx1YjJlNCEpIEFcdWM2NDAgQlx1YjI5NCAxIFx1Yzc3NFx1YzBjMSBOIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOTg0IFx1YmQ5OVx1YzVlY1x1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVhY2Y1XHVkMWI1IFx1Yzg3MFx1YzBjMVx1Yzc0NCBcdWFkNmNcdWQ1NjAgXHViNDUwIFx1YjE3OFx1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViY2M0XHViODVjLCBcdWNjYWIgXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViNDUwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDFiNSBcdWM4NzBcdWMwYzFcdWM3NDQgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM1ODQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOZWFyZXN0IENvbW1vbiBBbmNlc3RvcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcm9vdGVkIHRyZWUgaXMgYSB3ZWxsLWtub3duIGRhdGEgc3RydWN0dXJlIGluIGNvbXB1dGVyIHNjaWVuY2UgYW5kIGVuZ2luZWVyaW5nLiBBbiBleGFtcGxlIGlzIHNob3duIGJlbG93OjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMzXC9uY2EucG5nXCIgc3R5bGU9XCJoZWlnaHQ6Mjc4cHg7IHdpZHRoOjMwNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkluIHRoZSBmaWd1cmUsIGVhY2ggbm9kZSBpcyBsYWJlbGVkIHdpdGggYW4gaW50ZWdlciBmcm9tIHsxLCAyLCZoZWxsaXA7LDE2fS4gTm9kZSA4IGlzIHRoZSByb290IG9mIHRoZSB0cmVlLiBOb2RlIHggaXMgYW4gYW5jZXN0b3Igb2Ygbm9kZSB5IGlmIG5vZGUgeCBpcyBpbiB0aGUgcGF0aCBiZXR3ZWVuIHRoZSByb290IGFuZCBub2RlIHkuIEZvciBleGFtcGxlLCBub2RlIDQgaXMgYW4gYW5jZXN0b3Igb2Ygbm9kZSAxNi4gTm9kZSAxMCBpcyBhbHNvIGFuIGFuY2VzdG9yIG9mIG5vZGUgMTYuIEFzIGEgbWF0dGVyIG9mIGZhY3QsIG5vZGVzIDgsIDQsIDEwLCBhbmQgMTYgYXJlIHRoZSBhbmNlc3RvcnMgb2Ygbm9kZSAxNi4gUmVtZW1iZXIgdGhhdCBhIG5vZGUgaXMgYW4gYW5jZXN0b3Igb2YgaXRzZWxmLiBOb2RlcyA4LCA0LCA2LCBhbmQgNyBhcmUgdGhlIGFuY2VzdG9ycyBvZiBub2RlIDcuIEEgbm9kZSB4IGlzIGNhbGxlZCBhIGNvbW1vbiBhbmNlc3RvciBvZiB0d28gZGlmZmVyZW50IG5vZGVzIHkgYW5kIHogaWYgbm9kZSB4IGlzIGFuIGFuY2VzdG9yIG9mIG5vZGUgeSBhbmQgYW4gYW5jZXN0b3Igb2Ygbm9kZSB6LiBUaHVzLCBub2RlcyA4IGFuZCA0IGFyZSB0aGUgY29tbW9uIGFuY2VzdG9ycyBvZiBub2RlcyAxNiBhbmQgNy4gQSBub2RlIHggaXMgY2FsbGVkIHRoZSBuZWFyZXN0IGNvbW1vbiBhbmNlc3RvciBvZiBub2RlcyB5IGFuZCB6IGlmIHggaXMgYSBjb21tb24gYW5jZXN0b3Igb2YgeSBhbmQgeiBhbmQgbmVhcmVzdCB0byB5IGFuZCB6IGFtb25nIHRoZWlyIGNvbW1vbiBhbmNlc3RvcnMuIEhlbmNlLCB0aGUgbmVhcmVzdCBjb21tb24gYW5jZXN0b3Igb2Ygbm9kZXMgMTYgYW5kIDcgaXMgbm9kZSA0LiBOb2RlIDQgaXMgbmVhcmVyIHRvIG5vZGVzIDE2IGFuZCA3IHRoYW4gbm9kZSA4IGlzLjxcL3A+XHJcblxyXG48cD5Gb3Igb3RoZXIgZXhhbXBsZXMsIHRoZSBuZWFyZXN0IGNvbW1vbiBhbmNlc3RvciBvZiBub2RlcyAyIGFuZCAzIGlzIG5vZGUgMTAsIHRoZSBuZWFyZXN0IGNvbW1vbiBhbmNlc3RvciBvZiBub2RlcyA2IGFuZCAxMyBpcyBub2RlIDgsIGFuZCB0aGUgbmVhcmVzdCBjb21tb24gYW5jZXN0b3Igb2Ygbm9kZXMgNCBhbmQgMTIgaXMgbm9kZSA0LiBJbiB0aGUgbGFzdCBleGFtcGxlLCBpZiB5IGlzIGFuIGFuY2VzdG9yIG9mIHosIHRoZW4gdGhlIG5lYXJlc3QgY29tbW9uIGFuY2VzdG9yIG9mIHkgYW5kIHogaXMgeS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIG5lYXJlc3QgY29tbW9uIGFuY2VzdG9yIG9mIHR3byBkaXN0aW5jdCBub2RlcyBpbiBhIHRyZWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKFQgKSBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZS4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBOICwgdGhlIG51bWJlciBvZiBub2RlcyBpbiBhIHRyZWUsIDIgJmxlOyBOICZsZTsgMTAsMDAwIC4gVGhlIG5vZGVzIGFyZSBsYWJlbGVkIHdpdGggaW50ZWdlcnMgMSwyLC4uLixOIC4gRWFjaCBvZiB0aGUgbmV4dCBOICZtaW51czsxIGxpbmVzIGNvbnRhaW5zIGEgcGFpciBvZiBpbnRlZ2VycyB0aGF0IHJlcHJlc2VudCBhbiBlZGdlICZuZGFzaDsgdGhlIGZpcnN0IGludGVnZXIgaXMgdGhlIHBhcmVudCBub2RlIG9mIHRoZSBzZWNvbmQgaW50ZWdlci4gTm90ZSB0aGF0IGEgdHJlZSB3aXRoIE4gbm9kZXMgaGFzIGV4YWN0bHkgTiAmbWludXM7MSBlZGdlcy4gVGhlIGxhc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0d28gZGlzdGluY3QgaW50ZWdlcnMgd2hvc2UgbmVhcmVzdCBjb21tb24gYW5jZXN0b3IgaXMgdG8gYmUgY29tcHV0ZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG5lYXJlc3QgY29tbW9uIGFuY2VzdG9yLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2002 A번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)