BOJ 15586 - Moo tube ( 오프라인 쿼리, 유니온 파인드 )

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

왜 정답률이 65퍼인지 궁금한 문제

 

<문제설명>

자연수 가중치가 있는 트리가 주어진다.

 

정점 u~v경로 상의 가중 치 중 가장 작은 값을 usado(u,v)라고 한다.

 

최대 1e5개의 쿼리 (ki, vi)가 주어진다. vi와 연결된 정점 중 유사도가 ki이상인 정점의 수를 구하라.

 

<풀이>

V^2에 풀수있지만 TLE. 아예 다른방법으로 접근해야 한다.

 

임의의 정점에 대해 유사도 ki이상인 정점을 구하려면 가중치가 ki이상인 간선들만 필요하다.

->가중치가 ki 이상인 간선들로만 이뤄진 스패닝 트리를 두고 생각하면 편해진다.

 

쿼리를 ki에 대해 내림차순으로 정렬하고 간선도 가중치 기준으로 내림차순 정렬한다. 쿼리를 순차로 보면서, ki이상의 가중치를 가진 간선들만 이어주고, find(vi)집합의 크기를 반환하면 된다.

 

<코드>

typedef tuple<int, int, int> T;
const int MAX = 1e5 + 4;

int n, q, uf[MAX], sz[MAX];
T edge[MAX], query[MAX];
int find(int u) {
	if (uf[u] == -1) return u;
	return uf[u] = find(uf[u]);
}
void merge(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	uf[u] = v;
	sz[v] += sz[u];
	sz[u] = 1;
}
bool cmp(T t1, T t2) {return get<0>(t1) > get<0>(t2);}


int main() {
	FAST;
	memset(uf, -1, sizeof(uf));
    fill(sz,sz+MAX,1);
	cin >> n >> q;
	for (int i = 0, u, v, w; i < n-1; i++) {
		cin >> u >> v >> w;
		edge[i] = { w,u,v };
	}
	for (int i = 0, ki, vi; i < q; i++) {
		cin >> ki >> vi;
		query[i] = { ki,vi,i };
	}
	sort(edge, edge + n, cmp); //w,u,v
	sort(query, query + q, cmp); //ki,vi,i

	vector<int> ans(q);
	int j = 0;
	for (int i = 0; i < q; i++) {
		int ki, vi, idx;
		tie(ki, vi, idx) = query[i];
		while (j<n-1) {
			int w, u, v;
			tie(w, u, v) = edge[j];
			if (ki > w) break;
			merge(u, v);
			j++;
		}
		ans[idx] = sz[find(vi)]-1;
	}
	
	for (int i : ans)
		cout << i << '\n';
}

 

<생각>

완탐->dp로 풀리지 않는다. 시간은 둘째치고 메모리가 너무 부족하기 때문.

 

오프라인 쿼리 문제를 몇 개 풀어볼 필요가 있는 듯 하다.