Codeforces #627 : Div3. F. Maximum White Subtree

やはり最近のDiv3の方が難易度高いよなぁ。
https://codeforces.com/contest/1324/problem/F

問題

木を成す無向グラフが与えられる。
各点は白または黒の点で塗られている。

各点について、その点を含む連結部分グラフにおける、白点数-黒点数の最大値を求めよ。

解法

全方位木DPで、各SubTreeにおける白点数-黒点数を求めて行って、隣接点のSubTreeの前記値の総和を取ればよい。

int N;
int A[202020];
int sc[202020];
vector<int> E[202020];
int ret[202020];

int dfs(int cur,int pre) {
	ret[cur]=A[cur]?1:-1;
	FORR(e,E[cur]) if(e!=pre) {
		ret[cur]+=max(0,dfs(e,cur));
	}
	return ret[cur];
}

void dfs2(int cur,int pre,int p) {
	ret[cur]+=max(0,p);
	FORR(e,E[cur]) if(e!=pre) {
		dfs2(e,cur,ret[cur]-max(0,ret[e]));
	}
}

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;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	dfs2(0,0,0);
	FOR(i,N) cout<<ret[i]<<" ";
}

まとめ

なんで最近Div3難易度高めにしたんだろ。