풀이 자체는 쉬웠다.
간선에 parent와 children이라는 변수를 저장해서 셋팅한 후에 찾고자하는 두 노드의 공통 조상을 찾기 위해 첫 번째 target1의 공통 조상을 모두 set 자료구조에 담고, 이후 두 번째 target2의 공통 조상을 탐색하면서 해당 조상이 set에 이미 저장된 조상인지 확인한 후에 출력했다.
구현력 자체가 문제인거지 생각자체는 쉬웠던 풀이.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const solution = (N, data) => {
const arr = Array.from(Array(N + 1), () => ({
parent: null,
children: new Array(),
}));
for (let i = 0; i < N - 1; i++) {
const [parent, child] = data[i];
arr[parent].children.push(child);
arr[child].parent = parent;
}
const [target1, target2] = data.pop();
const cache = new Set();
let tmp = target1;
while (tmp) {
cache.add(tmp);
tmp = arr[tmp].parent;
}
tmp = target2;
while (tmp) {
if (cache.has(tmp)) {
answer += `${tmp}\n`;
break;
}
tmp = arr[tmp].parent;
}
};
let answer = '';
let T = Number(input[0]);
let cur = 1;
while (T--) {
const N = Number(input[cur++]);
const data = input.slice(cur, cur + N).map((v) => v.split(' ').map(Number));
cur += N;
solution(N, data);
}
console.log(answer);