Node.js)백준 11437번 : LCA

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

 

// https://www.acmicpc.net/problem/11437
class Node {
	constructor(index) {
		this.index = index;
		this.parent = null;
		this.height = null;
		this.adj = [];
	}

	setHeight(p) {
		this.parent = p;
		this.height = p == -1 ? 0 : nodes[p].height + 1;
		this.adj.forEach((child) => {
			if (child != this.parent) {
				nodes[child].setHeight(this.index);
			}
		});
	}
}
const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const N = input.shift()[0];
const nodes = Array.from(new Array(N), (_, i) => new Node(i));

const edges = input.splice(0, N - 1);
edges.forEach(([a, b]) => {
	nodes[a - 1].adj.push(b - 1);
	nodes[b - 1].adj.push(a - 1);
});
nodes[0].setHeight(-1);
// console.log(nodes.map((v) => v.height));
const T = input.shift();
const tc = input;

const answer = tc.map((v) => {
	const [a, b] = v.map((w) => w - 1);
	let A = nodes[a];
	let B = nodes[b];

	while (A.height > B.height) {
		A = nodes[A.parent];
	}

	while (B.height > A.height) {
		B = nodes[B.parent];
	}

	while (B.index != A.index) {
		A = nodes[A.parent];
		B = nodes[B.parent];
	}

	return A.index + 1;
});

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