Codeforces #635 Div1 A. Linova and Kingdom

なんか妙に調子がいいと思ったら6連続レート増してる時だった。
https://codeforces.com/contest/1336/problem/A

問題

根付き木を成す無向グラフが与えられる。
ここからK個の点を選んだとする。
選んだ点のスコアを、根からその点へのパスにおける頂点のうち、選んでない頂点数とする。
スコアの総和の最大値を求めよ。

解法

葉に近いほどスコアが良いのは自明なので、ある頂点を選ぶのはsubtreeの頂点内で最後となる。
よって、ある点を選ぶときのスコアの増分は、その点が選択されたことにより深さ分スコアが増す一方で、Subtree内の頂点のスコアが頂点毎に1ずつ減ることになる。

そこで、この増分をソートし、上位K個を選ぼう。

int N,K;
vector<int> E[202020];
int D[202020];
int C[202020];

int dfs(int cur,int pre) {
	if(cur) D[cur]=D[pre]+1;
	C[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		C[cur]+=dfs(e,cur);
	}
	return C[cur];
}

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);
	}
	
	dfs(0,0);
	vector<int> V;
	FOR(i,N) V.push_back(D[i]-(C[i]-1));
	sort(ALL(V));
	reverse(ALL(V));
	ll ret=0;
	FOR(i,K) ret+=V[i];
	cout<<ret<<endl;
}

まとめ

Aで木が出るのは珍しいイメージ。