BOJ 16011 Min Max Tree

Min Max Tree

문제풀면서 이렇게 코드를 길게짜보긴 처음이다. 줄일 여지가 충분히 많긴 했지만 구현 연습하는셈치고 하나하나 다 짰다.

일단 어떤 경로 상에서 최솟값이 \(z\)라는 것은 그 경로상의 간선은 \(z\)이상이라는 의미다.
마찬가지로 최댓값이 주어지면 \(z\)이하라는 의미다.

그러면 이제 주어진 정보들을 가지고 모든 간선의 범위를 정할 수 있다. 문제는 어떤 경로 상의 구간의 최댓값과 최솟값을 업데이트해야한다는건데, 이거는 트리를 HLD로 나눈 뒤에 세그먼트 트리로 하면 된다.

그리고 모든 간선들의 범위를 정했다면, 원래 주어진 정보에 맞춰줘야 한다.
최솟값에 대한 정보였다면 그 경로에는 적어도 하나의 그 값이 있어야 한다.
이건 그리디하게? 하면 되는데,
각 정보 별로 값을 배정할 수 있는 간선들이 있을 것이다. 그러면 그 간선의 개수가 적은 것부터 배정할 수 있는 간선 중 아무거나 배정하면 된다.
만약 그 간선이 하나라면 무조건 그 간선에 값을 배정해야하므로 이 정보를 먼저 해결해야 한다.
그리고 그 간선이 두 개 이상이라면 배정할 수 있는 것 중 아무거나 배정해도 다른 정보 중에 하나에만 영향을 끼친다.
그러니까 아무거나 되는 것 중에서 골라도 상관없다.

그래서 짠게 LCA, HLD, 세그먼트트리 + Lazy Propagation라서 코드가 엄청 길어졌다. 근데 다른 분들 코드를 보니까 이분 매칭으로도 풀리는 것 같기도 하다.

#include <bits/stdc++.h>

using namespace std;

const int ninf = -2e9, pinf = 2e9;

struct Qry {
	bool mx;
	int u, v, w;
};

vector<int> gph[70001], rng[70001];
Qry qry[70001];
int n, dep[70001], subsz[70001], ord[70001], num, par[70001][20], chain[70001], chainhead[70001], chainnum, mnlazy[500000], mntree[500000], mxlazy[500000], mxtree[500000], cnt[70001], low[70001], high[70001], ans[70001], rord[70001];
bool comp[70001], compans[70001];

int f(int now, int d) {
	dep[now] = d;
	subsz[now] = 1;

	for (int i = 1; i < 20; ++i)
		par[now][i] = par[par[now][i - 1]][i - 1];

	for (int nxt : gph[now])
		if (nxt != par[now][0]) {
			par[nxt][0] = now;
			subsz[now] += f(nxt, d + 1);
		}

	return subsz[now];
}

void mkchain(int now) {
	ord[now] = ++num;
	chain[now] = chainnum;

	int heavy = 0, heavyi = -1;
	for (int nxt : gph[now])
		if (nxt != par[now][0] && heavy < subsz[nxt]) {
			heavy = subsz[nxt];
			heavyi = nxt;
		}

	if (heavyi != -1)
		mkchain(heavyi);

	for (int nxt : gph[now])
		if (nxt != par[now][0] && nxt != heavyi) {
			chainnum++;
			chainhead[chainnum] = nxt;
			mkchain(nxt);
		}
}

int lca(int u, int v) {
	if (dep[u] < dep[v])
		swap(u, v);

	for (int i = 19; i >= 0; --i)
		if (dep[par[u][i]] >= dep[v])
			u = par[u][i];

	if (u == v)
		return u;

	for (int i = 19;i >= 0;--i)
		if (par[u][i] != par[v][i]) {
			u = par[u][i];
			v = par[v][i];
		}

	return par[u][0];
}

void lazymn(int l, int r, int idx) {
	mntree[idx] = max(mntree[idx], mnlazy[idx]);

	if (l != r) {
		mnlazy[idx * 2] = max(mnlazy[idx * 2], mnlazy[idx]);
		mnlazy[idx * 2 + 1] = max(mnlazy[idx * 2 + 1], mnlazy[idx]);
	}

	mnlazy[idx] = ninf;
}

int updmn(int l, int r, int idx, int s, int e, int val) {
	lazymn(l, r, idx);

	if (e < l || r < s)
		return mntree[idx];
	if (s <= l && r <= e) {
		mntree[idx] = max(mntree[idx], val);
		if (l != r) {
			mnlazy[idx * 2] = max(mnlazy[idx * 2], val);
			mnlazy[idx * 2 + 1] = max(mnlazy[idx * 2 + 1], val);
		}
		return mntree[idx];
	}
	
	int m = (l + r) / 2;
	return mntree[idx] = max(updmn(l, m, idx * 2, s, e, val), updmn(m + 1, r, idx * 2 + 1, s, e, val));
}

int qrymn(int l, int r, int idx, int s, int e) {
	lazymn(l, r, idx);

	if (e < l || r < s)
		return ninf;
	if (s <= l && r <= e)
		return mntree[idx];

	int m = (l + r) / 2;
	return max(qrymn(l, m, idx * 2, s, e), qrymn(m + 1, r, idx * 2 + 1, s, e));
}

void lazymx(int l, int r, int idx) {
	mxtree[idx] = min(mxtree[idx], mxlazy[idx]);
	if (l != r) {
		mxlazy[idx * 2] = min(mxlazy[idx * 2], mxlazy[idx]);
		mxlazy[idx * 2 + 1] = min(mxlazy[idx * 2 + 1], mxlazy[idx]);
	}

	mxlazy[idx] = pinf;
}

int updmx(int l, int r, int idx, int s, int e, int val) {
	lazymx(l, r, idx);
	if (e < l || r < s)
		return mxtree[idx];
	if (s <= l && r <= e) {
		mxtree[idx] = min(mxtree[idx], val);
		if (l != r) {
			mxlazy[idx * 2] = min(mxlazy[idx * 2], val);
			mxlazy[idx * 2 + 1] = min(mxlazy[idx * 2 + 1], val);
		}
		return mxtree[idx];
	}

	int m = (l + r) / 2;
	return mxtree[idx] = min(updmx(l, m, idx * 2, s, e, val), updmx(m + 1, r, idx * 2 + 1, s, e, val));
}

int qrymx(int l, int r, int idx, int s, int e) {
	lazymx(l, r, idx);
	if (e < l || r < s)
		return pinf;
	if (s <= l && r <= e)
		return mxtree[idx];

	int m = (l + r) / 2;
	return min(qrymx(l, m, idx * 2, s, e), qrymx(m + 1, r, idx * 2 + 1, s, e));
}

void mkrange(int u, int v, bool mx, int val) {
	if (dep[u] < dep[v])
		swap(u, v);

	if (u == v)
		return;

	if (chain[u] == chain[v]) {
		if (mx)
			updmx(1, n, 1, ord[v] + 1, ord[u], val);
		else
			updmn(1, n, 1, ord[v] + 1, ord[u], val);
	}
	else {
		if (mx) {
			updmx(1, n, 1, ord[chainhead[chain[u]]], ord[u], val);
			mkrange(par[chainhead[chain[u]]][0], v, mx, val);
		}
		else {
			updmn(1, n, 1, ord[chainhead[chain[u]]], ord[u], val);
			mkrange(par[chainhead[chain[u]]][0], v, mx, val);
		}
	}
}

int main() {
	scanf("%d", &n);

	for (int i = 1; i <= n - 1; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);

		gph[u].push_back(v);
		gph[v].push_back(u);
	}

	int k;
	scanf("%d", &k);

	for (int i = 1; i <= k; ++i) {
		char c;
		scanf(" %c %d %d %d", &c, &qry[i].u, &qry[i].v, &qry[i].w);

		if (c == 'M')
			qry[i].mx = true;
		else
			qry[i].mx = false;
	}

	f(1, 1);
	chainnum++;
	chainhead[chainnum] = 1;
	mkchain(1);

	for (int i = 0; i < 500000; ++i) {
		mnlazy[i] = ninf;
		mntree[i] = ninf;
		mxlazy[i] = pinf;
		mxtree[i] = pinf;
	}

	for (int i = 1; i <= k; ++i) {
		int l = lca(qry[i].u, qry[i].v);

		mkrange(qry[i].u, l, qry[i].mx, qry[i].w);
		mkrange(qry[i].v, l, qry[i].mx, qry[i].w);
	}

	map<int, int> dic;
	for (int i = 1; i <= k; ++i)
		dic[qry[i].w] = i;
	for (int i = 2; i <= n; ++i) {
		low[i] = qrymn(1, n, 1, i, i);
		high[i] = qrymx(1, n, 1, i, i);

		if (low[i] != ninf) {
			cnt[dic[low[i]]]++;
			rng[dic[low[i]]].push_back(i);
		}
		if (high[i] != pinf) {
			cnt[dic[high[i]]]++;
			rng[dic[high[i]]].push_back(i);
		}
	}

	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	for (int i = 1; i <= k; ++i)
		pq.push({ cnt[dic[qry[i].w]], i });
	while (!pq.empty()) {
		pair<int, int> now = pq.top();
		pq.pop();

		if (now.first != cnt[now.second])
			continue;

		comp[now.second] = true;

		for (int cand : rng[now.second])
			if (!compans[cand]) {
				ans[cand] = qry[now.second].w;
				compans[cand] = true;
				if (qry[now.second].mx) {
					if (low[cand] != ninf) {
						cnt[dic[low[cand]]]--;

						if (!comp[dic[low[cand]]])
							pq.push({ cnt[dic[low[cand]]], dic[low[cand]] });
					}
				}
				else {
					if (high[cand] != pinf) {
						cnt[dic[high[cand]]]--;

						if (!comp[dic[high[cand]]])
							pq.push({ cnt[dic[high[cand]]], dic[high[cand]] });
					}
				}

				break;
			}
	}

	for (int i = 2; i <= n; ++i)
		if (!compans[i]) {
			ans[i] = low[i];
			compans[i] = true;
		}

	for (int i = 1; i <= n; ++i)
		rord[ord[i]] = i;

	for (int i = 2; i <= n; ++i)
		printf("%d %d %d\n", rord[i], par[rord[i]][0], ans[i]);

	return 0;
}