Codeforces #525 Div2 E. Ehab and a component choosing problem

本番詰め切れなかった。
https://codeforces.com/contest/1088/problem/E

問題

N頂点の木を成すグラフが与えられる。
各頂点にはスコアが設定されている。

ここから、互いに共通部分を持たないいくつかの連結成分を抜き出すことを考える。
各連結成分内の全頂点のスコアの総和について、連結成分内の平均を最大化したい。
その時の平均値を求めよ。

また、平均値が同着な範囲で、連結成分数の最大値を求めよ。

解法

複数の連結成分がある場合、全てがスコアの総和が一致しない限り、それらを含む理由がない。
一部スコアの総和が高いなら、それらだけを抜き出した方が平均が高まる。

よって、以下の２ステップに分けて解く。

• 部分木のうちスコアの総和の最大値を求める
• 最大値が一致する連結成分数を求める

前者は容易で、子頂点を根とする部分木のスコアの総和が正なら親と連結する、ということを葉から順に行っていけばよい。
後者も、同じ手順を繰り返しスコアの総和が最大値と一致するタイミングを列挙するだけ。

int N;
int A[303030];
ll S[303030];
vector<int> E[303030];

ll ma[303030];
ll ret;
int ret2;

void dfs(int cur,int pre) {
	ma[cur]=A[cur];
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		if(ma[e]>0) ma[cur]+=ma[e];
	}
}

void dfs2(int cur,int pre) {
	ma[cur]=A[cur];
	FORR(e,E[cur]) if(e!=pre) {
		dfs2(e,cur);
		if(ma[e]>0) ma[cur]+=ma[e];
	}
	if(ma[cur]==ret) {
		ret2++;
		ma[cur]=-1LL<<60;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	
	dfs(0,-1);
	ret=*max_element(ma,ma+N);
	dfs2(0,-1);
	
	cout<<ret*ret2<<" "<<ret2<<endl;
	
}

まとめ

うーん、本番詰めが甘かった。