Centroid Decomposition

트리에서 센트로이드를 잡고 분할 정복을 돌리는 테크닉.

 

5820번: 경주

 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+1;
const int K=1e6+1;
const int INF=1e9;
int n,k;
int sz[N],use[N],chk[K];
vector<pii> ad[N];
vector<int> tree;
int get_size(int cur,int prv) {
	sz[cur]=1;
	for(auto [nxt,w] : ad[cur]){
		if(nxt==prv||use[nxt]) continue;
		sz[cur]+=get_size(nxt,cur);
	}
	return sz[cur];
}
int get_cent(int cur,int prv,int cap) {
	for(auto [nxt,w] : ad[cur]){
		if(nxt==prv||use[nxt]) continue;
		if(sz[nxt]>cap) return get_cent(nxt,cur,cap);
	}
	return cur;
}
int solve(int cur,int prv,int dis,int dep) {
	int ret=INF;
	if(dis>k) return ret;
	ret=min(ret,chk[k-dis]+dep);
	for(auto [nxt,w] : ad[cur]){
		if(nxt==prv||use[nxt]) continue;
		ret=min(ret,solve(nxt,cur,dis+w,dep+1));
	}
	return ret;
}
void update(int cur,int prv,int dis,int dep) {
	if(dis>k) return;
	chk[dis]=min(chk[dis],dep);
	tree.push_back(dis);
	for(auto [nxt,w] : ad[cur]){
		if(nxt==prv||use[nxt]) continue;
		update(nxt,cur,dis+w,dep+1);
	}
}
int dnc(int cur) {
	int cap=get_size(cur,-1);
	int cent=get_cent(cur,-1,cap/2);
	int ret=INF;
	for(auto it : tree) chk[it]=INF;
	tree.clear();
	use[cent]=1, chk[0]=0;
	for(auto [nxt,w] : ad[cent]){
		if(use[nxt]) continue;
		ret=min(ret,solve(nxt,cent,w,1));
		update(nxt,cent,w,1);
	}
	for(auto [nxt,w] : ad[cent]){
		if(use[nxt]) continue;
		ret=min(ret,dnc(nxt));
	}
	return ret;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> k;
	for(int i=1;i<n;i++){
		int u,v,w; cin >> u >> v >> w;
		ad[u].push_back({v,w});
		ad[v].push_back({u,w});
	}
	fill(chk,chk+k+1,INF);
	int ans=dnc(0);
	cout << (ans==INF?-1:ans);
}