24520 - Meet In The Middle

step 1

신촌 왕국은 트리 구조로 되어 있습니다. 두 사람의 위치가 s, e라고 하겠습니다.

 

1번 영역은 항상 s가 더 가깝습니다.

2번 영역은 항상 e가 더 가깝습니다.

만약 초록색 점이 답이라고 가정하면 빨간 점이 각 마을까지 거리의 합이 더 짧으므로 모순이 생깁니다.

즉, s와 e 사이의 경로에 답이 있습니다.

step 2

LCA를 이용해서 두 점 사이의 거리를 구할 수 있습니다. 

그리고 LCA를 이용해서 s나 e에서 특정 거리만큼 떨어진 경로 위의 점을 구할 수 있습니다.

LCA를 구할 때 dfs로 하면 메모리가 터질 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<pair<long long int, long long int>> v[200000];
queue<pair<long long int, long long int>> qq;
long long int mapp[200000][30],lv[200000], mapg[200000][30];
long long int gx, gy;
long long int lca(long long int x, long long int y) {
	long long int p = lv[y] - lv[x], i;
	for (i = 20;i >= 0;i--) {
		if (p >= (1 << i)) {
			gy += mapg[y][i];
			y = mapp[y][i];
			p -= (1 << i);
		}
	}
	if (x == y) return x;
	for (i = 20;i >= 0;i--) {
		if (mapp[x][i] != mapp[y][i]) {
			gx += mapg[x][i];
			gy += mapg[y][i];
			x = mapp[x][i];
			y = mapp[y][i];
		}
	}
	gx += mapg[x][0];
	gy += mapg[y][0];
	x = mapp[x][0];
	y = mapp[y][0];
	return x;
}
long long int up(long long int i, long long int g) {
	long long int j;
	for (j = 20;j >= 0;j--) {
		if (mapp[i][j] == 0) continue;
		if (g >= mapg[i][j]) {
			g -= mapg[i][j];
			i = mapp[i][j];
		}
	}
	if (g == 0) return i;
	else return -1;
}
int main() {
	long long int n, q, i, j;
	scanf("%lld%lld", &n, &q);
	for (i = 1;i < n;i++) {
		long long int x, y, z;
		scanf("%lld%lld%lld", &x, &y, &z);
		//x = i; y = i + 1; z = 1000000000;
		v[x].push_back({ y,z });
		v[y].push_back({ x,z });
	}
	qq.push({ 1,0 });
	while (qq.size()) {
		int i = qq.front().first, p = qq.front().second;
		qq.pop();
		mapp[i][0] = p;
		lv[i] = lv[p] + 1;
		for (j = 1;j < 20;j++) {
			mapp[i][j] = mapp[mapp[i][j - 1]][j - 1];
			mapg[i][j] = mapg[i][j - 1] + mapg[mapp[i][j - 1]][j - 1];
		}
		for (j = 0;j < v[i].size();j++) {
			if (v[i][j].first == p) continue;
			mapg[v[i][j].first][0] = v[i][j].second;
			qq.push({ v[i][j].first, i });
		}
	}
 	while (q--) {
		long long int x, y,p;
		scanf("%lld%lld", &x, &y);
		gx = 0; gy = 0;
		if (lv[x] > lv[y]) swap(x, y);
		p = lca(x, y);
		if ((gx + gy) % 2 != 0) { printf("-1\n"); continue; }
		if (gx == gy) { printf("%lld\n", p); continue; }
		else if (gx > gy) printf("%lld\n", up(x, (gx + gy) / 2));
		else if (gx < gy) printf("%lld\n", up(y, (gx + gy) / 2));
	}
	return 0;
}