Codeforces #1023 : Div2 E. Ain and Apple Tree

コードは短め。
https://codeforces.com/contest/2107/problem/E

問題

根付き木の重さとは、全頂点対における、LCAの深さの総和とする。
整数N,Kが与えられるので、N頂点の木のうち、重さがK±1の範囲に収まるものを構成せよ。

解法

作りえる重さの最大値はパスグラフのものであり、Kがそれを超える場合は解なし。
パスグラフから初めて、重さを減らしていくことを考える。
頂点番号の大きい順に、重さを少しずつ減らすよう点を根に近づけていこう。

int T;
ll N,K;

ll comb2(ll a) {
	return a*(a-1)/2;
}
ll comb3(ll a) {
	return a*(a-1)*(a-2)/6;
}
int P[202020];
	

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		if(K>comb3(N)+1) {
			cout<<"No"<<endl;
			continue;
		}
		cout<<"Yes"<<endl;
		K=max(0LL,comb3(N)-K);
		int ma=N-1;
		for(i=N-1;i>0;i--) {
			while(comb2(ma)>K) ma--;
			K-=comb2(ma);
			cout<<i+1<<" "<<i+1-ma<<endl;
			if(ma>1) ma--;
		}
		assert(abs(K)<=1);
	}
}

まとめ

終わってみると解法はシンプル。