Node.js) 백준 3584: 가장 가까운 공통 조상

https://www.acmicpc.net/problem/3584

 

// https://www.acmicpc.net/problem/3584

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
let index = 0;

class Node {
	constructor(value) {
		this.value = value;
		this.height = -1;
		this.parent = null;
		this.children = [];
	}

	setHeight(number) {
		this.height = number;
		this.children.forEach((child) => {
			child.setHeight(number + 1);
		});
	}
}

const T = input[index++][0];
const answer = [];
for (let t = 0; t < T; t++) {
	const N = input[index++][0];
	const nodes = Array.from(new Array(N), (v, k) => new Node(k));
	for (let n = 1; n < N; n++) {
		const [p, c] = input[index++].map((v) => v - 1);
		nodes[p].children.push(nodes[c]);
		nodes[c].parent = nodes[p];
	}
	const root = nodes.find((v) => v.parent == null);
	root.setHeight(0);

	let [t1, t2] = input[index++].map((v) => nodes[v - 1]);
	while (t1.height > t2.height) {
		t1 = t1.parent;
	}

	while (t1.height < t2.height) {
		t2 = t2.parent;
	}

	while (t1.value != t2.value) {
		t1 = t1.parent;
		t2 = t2.parent;
	}

	answer.push(t1.value + 1);
}

console.log(answer.join('\n'));