CodeTON Round 5 : F. Tenzing and Tree

F問題の割にコードは短い。
https://codeforces.com/contest/1842/problem/F

問題

N点の木を成す無向グラフを考える。
各点を白黒で塗ったとき、木のスコアは以下のように計算される。

• 各辺を削除したとき、両連結成分の黒点の数の差の絶対値の総和

黒く塗る点をK個任意に選べるとき、スコアの最大値を求めたい。
K=1～Nについてそれぞれ求めよ。

解法

木の中心から近い順にK個選ぶのが最適。
木の中心の位置はN通り総当たりしてしまえばよい。

int N;
vector<int> E[5050];
int ret[5050];
int D[5050];

void solve() {
	int i,j,k,l,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) {
		queue<int> Q;
		MINUS(D);
		D[i]=0;
		Q.push(i);
		int sum=0;
		int step=1;
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			
			sum+=D[x];
			ret[step]=max(ret[step],(N-1)*step-sum*2);
			step++;
			FORR(e,E[x]) if(D[e]==-1) {
				D[e]=D[x]+1;
				Q.push(e);
			}
		}
	}
	
	
	
	FOR(i,N+1) cout<<ret[i]<<" ";
	cout<<endl;
	
	
	
}

まとめ

意外に力技。