FII Code 2020 Round #2 : D. Disproportionate Tree

Eがすんなり解けたおかげで良い順位。
https://csacademy.com/contest/fii-code-2020-round-2/task/disproportionate-tree/

問題

無向グラフと整数Kが与えられる。
各頂点に整数値V[i]をふったとき、u,vをつなぐ辺の重さは2^|V[u]-V[v]|となる。
辺の重さの合計をKとできるVの割り当てを求めよ。

解法

辺の重さは2の累乗の値をとれることになる。
最小で各辺に1をふるとし、追加で(2^i-1)の形の重さを辺毎に追加できると考える。
これは貪欲にに振れる範囲で最大値を追加していけばよい。

int N;
vector<int> E[101010];
int K;

int ret[101010];
vector<int> C;

void dfs(int cur,int pre,int d) {
	ret[cur]=d;
	FORR(e,E[cur]) if(e!=pre) {
		int x=C.back();
		C.pop_back();
		dfs(e,cur,d-x);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	if(K<N-1) return _P("NO\n");
	K-=(N-1);
	for(i=29;i>=1;i--) {
		while(K>=((1<<i)-1)) {
			C.push_back(i);
			K-=((1<<i)-1);
		}
	}
	if(C.size()>N-1) return _P("NO\n");
	FOR(i,N) C.push_back(0);
	sort(ALL(C));
	dfs(0,0,100000);
	cout<<"YES"<<endl;
	FOR(i,N) cout<<ret[i]<<" ";
}

まとめ

ここまでは割と簡単。