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

문제

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

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

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
W3sicHJvYmxlbV9pZCI6IjM1ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDFiNSBcdWM4NzBcdWMwYzEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjhlOFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjKHJvb3RlZCB0cmVlKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWQyYjhcdWI5YWMgXHVjMGMxXHVjNzU4IFx1YjQ1MCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWFkZjhcdWI0ZTRcdWM3NTggXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjZjVcdWQxYjUgXHVjODcwXHVjMGMxKE5lYXJlc3QgQ29tbW9uIEFuc2Nlc3RvcilcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViNDUwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDFiNSBcdWM4NzBcdWMwYzFcdWM3NDAsIFx1YjQ1MCBcdWIxNzhcdWI0ZGNcdWI5N2MgXHViYWE4XHViNDUwIFx1Yzc5MFx1YzE5MFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM5YzBcdWJhNzRcdWMxMWMgXHVhZTRhXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWFlNGFcdWM3NDAoXHVjOTg5IFx1YjQ1MCBcdWIxNzhcdWI0ZGNcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCkgXHViMTc4XHViNGRjXHViOTdjIFx1YjlkMFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJuY2EucG5nXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNGYyZWFlNTgtMzFiZi00NDVmLWE3YTMtNjI1NTA1ZTcxMDJjXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cImhlaWdodDoyNzhweDsgd2lkdGg6MzA0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCZuYnNwOyAxNVx1YzY0MCAxMVx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjNzkwXHVjMTkwXHVjNzNjXHViODVjIFx1YWMxNlx1YjI5NCBcdWIxNzhcdWI0ZGNcdWIyOTQgNFx1YzY0MCA4XHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYywgXHVhZGY4IFx1YzkxMSBcdWFlNGFcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YWU0YVx1Yzc0MCgxNVx1YzY0MCAxMVx1YzVkMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0KSBcdWIxNzhcdWI0ZGNcdWIyOTQgNCBcdWM3NzRcdWJiYzBcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjZjVcdWQxYjUgXHVjODcwXHVjMGMxXHVjNzQwIDRcdWFjMDAgXHViNDI5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4ZThcdWQyYjhcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1MCBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWFkZjggXHViNDUwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNmNVx1ZDFiNSBcdWM4NzBcdWMwYzFcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMxMzhcdWM2OTQ8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YjJlNFx1Yzc0YyBOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHVhYzA0XHVjMTIwIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1ZDU1YyBcdWFjMDRcdWMxMjAgXHViMmY5IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTAgQSBCIFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgQVx1YWMwMCBCXHVjNzU4IFx1YmQ4MFx1YmFhOFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3ODVcdWIyYzhcdWIyZTQuIChcdWIyZjlcdWM1ZjBcdWQ3ODggXHVjODE1XHVjODEwXHVjNzc0IE5cdWFjMWNcdWM3NzggXHVkMmI4XHViOWFjXHViMjk0IFx1ZDU2ZFx1YzBjMSBOLTFcdWFjMWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzlkMVx1YjJjOFx1YjJlNCEpIEFcdWM2NDAgQlx1YjI5NCAxJm5ic3A7XHVjNzc0XHVjMGMxIE4gXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI5ODQgXHViZDk5XHVjNWVjXHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjZjVcdWQxYjUgXHVjODcwXHVjMGMxXHVjNzQ0IFx1YWQ2Y1x1ZDU2MCBcdWI0NTAgXHViMTc4XHViNGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjYzRcdWI4NWMsIFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWI0NTAgXHViMTc4XHViNGRjXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVhY2Y1XHVkMWI1IFx1Yzg3MFx1YzBjMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzU4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5lYXJlc3QgQ29tbW9uIEFuY2VzdG9ycyIsImRlc2NyaXB0aW9uIjoiPHA+QSByb290ZWQgdHJlZSBpcyBhIHdlbGwta25vd24gZGF0YSBzdHJ1Y3R1cmUgaW4gY29tcHV0ZXIgc2NpZW5jZSBhbmQgZW5naW5lZXJpbmcuIEFuIGV4YW1wbGUgaXMgc2hvd24gYmVsb3c6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczNcL25jYS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNzhweDsgd2lkdGg6MzA0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGZpZ3VyZSwgZWFjaCBub2RlIGlzIGxhYmVsZWQgd2l0aCBhbiBpbnRlZ2VyIGZyb20gezEsIDIsJmhlbGxpcDssMTZ9LiBOb2RlIDggaXMgdGhlIHJvb3Qgb2YgdGhlIHRyZWUuIE5vZGUgeCBpcyBhbiBhbmNlc3RvciBvZiBub2RlIHkgaWYgbm9kZSB4IGlzIGluIHRoZSBwYXRoIGJldHdlZW4gdGhlIHJvb3QgYW5kIG5vZGUgeS4gRm9yIGV4YW1wbGUsIG5vZGUgNCBpcyBhbiBhbmNlc3RvciBvZiBub2RlIDE2LiBOb2RlIDEwIGlzIGFsc28gYW4gYW5jZXN0b3Igb2Ygbm9kZSAxNi4gQXMgYSBtYXR0ZXIgb2YgZmFjdCwgbm9kZXMgOCwgNCwgMTAsIGFuZCAxNiBhcmUgdGhlIGFuY2VzdG9ycyBvZiBub2RlIDE2LiBSZW1lbWJlciB0aGF0IGEgbm9kZSBpcyBhbiBhbmNlc3RvciBvZiBpdHNlbGYuIE5vZGVzIDgsIDQsIDYsIGFuZCA3IGFyZSB0aGUgYW5jZXN0b3JzIG9mIG5vZGUgNy4gQSBub2RlIHggaXMgY2FsbGVkIGEgY29tbW9uIGFuY2VzdG9yIG9mIHR3byBkaWZmZXJlbnQgbm9kZXMgeSBhbmQgeiBpZiBub2RlIHggaXMgYW4gYW5jZXN0b3Igb2Ygbm9kZSB5IGFuZCBhbiBhbmNlc3RvciBvZiBub2RlIHouIFRodXMsIG5vZGVzIDggYW5kIDQgYXJlIHRoZSBjb21tb24gYW5jZXN0b3JzIG9mIG5vZGVzIDE2IGFuZCA3LiBBIG5vZGUgeCBpcyBjYWxsZWQgdGhlIG5lYXJlc3QgY29tbW9uIGFuY2VzdG9yIG9mIG5vZGVzIHkgYW5kIHogaWYgeCBpcyBhIGNvbW1vbiBhbmNlc3RvciBvZiB5IGFuZCB6IGFuZCBuZWFyZXN0IHRvIHkgYW5kIHogYW1vbmcgdGhlaXIgY29tbW9uIGFuY2VzdG9ycy4gSGVuY2UsIHRoZSBuZWFyZXN0IGNvbW1vbiBhbmNlc3RvciBvZiBub2RlcyAxNiBhbmQgNyBpcyBub2RlIDQuIE5vZGUgNCBpcyBuZWFyZXIgdG8gbm9kZXMgMTYgYW5kIDcgdGhhbiBub2RlIDggaXMuPFwvcD5cclxuXHJcbjxwPkZvciBvdGhlciBleGFtcGxlcywgdGhlIG5lYXJlc3QgY29tbW9uIGFuY2VzdG9yIG9mIG5vZGVzIDIgYW5kIDMgaXMgbm9kZSAxMCwgdGhlIG5lYXJlc3QgY29tbW9uIGFuY2VzdG9yIG9mIG5vZGVzIDYgYW5kIDEzIGlzIG5vZGUgOCwgYW5kIHRoZSBuZWFyZXN0IGNvbW1vbiBhbmNlc3RvciBvZiBub2RlcyA0IGFuZCAxMiBpcyBub2RlIDQuIEluIHRoZSBsYXN0IGV4YW1wbGUsIGlmIHkgaXMgYW4gYW5jZXN0b3Igb2YgeiwgdGhlbiB0aGUgbmVhcmVzdCBjb21tb24gYW5jZXN0b3Igb2YgeSBhbmQgeiBpcyB5LjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgbmVhcmVzdCBjb21tb24gYW5jZXN0b3Igb2YgdHdvIGRpc3RpbmN0IG5vZGVzIGluIGEgdHJlZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoVCApIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIE4gLCB0aGUgbnVtYmVyIG9mIG5vZGVzIGluIGEgdHJlZSwgMiAmbGU7IE4gJmxlOyAxMCwwMDAgLiBUaGUgbm9kZXMgYXJlIGxhYmVsZWQgd2l0aCBpbnRlZ2VycyAxLDIsLi4uLE4gLiBFYWNoIG9mIHRoZSBuZXh0IE4gJm1pbnVzOzEgbGluZXMgY29udGFpbnMgYSBwYWlyIG9mIGludGVnZXJzIHRoYXQgcmVwcmVzZW50IGFuIGVkZ2UgJm5kYXNoOyB0aGUgZmlyc3QgaW50ZWdlciBpcyB0aGUgcGFyZW50IG5vZGUgb2YgdGhlIHNlY29uZCBpbnRlZ2VyLiBOb3RlIHRoYXQgYSB0cmVlIHdpdGggTiBub2RlcyBoYXMgZXhhY3RseSBOICZtaW51czsxIGVkZ2VzLiBUaGUgbGFzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBkaXN0aW5jdCBpbnRlZ2VycyB3aG9zZSBuZWFyZXN0IGNvbW1vbiBhbmNlc3RvciBpcyB0byBiZSBjb21wdXRlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIGludGVnZXIgdGhhdCBpcyB0aGUgbmVhcmVzdCBjb21tb24gYW5jZXN0b3IuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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