Codeforces #527: Div3. F. Tree with Maximum Cost

問題

木を成す無向グラフが与えられる。
また、各点vには設定値A[v]がある。

どこかの点rを根としたとき、この木のスコアは、各点vの設定値A[v]と(r,v)間の距離の積和とする。
スコアの最大値を求めよ。

解法

全方位木DPで、SubTree内のスコアとA[v]の総和を求めて行くだけ。

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


void dfs(int cur,int pre,int d) {;
	S[0]+=A[cur]*d;
	SA[cur]=A[cur];
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur,d+1);
		SA[cur]+=SA[e];
	}
	
}

void dfs2(int cur,int pre) {
	if(pre!=-1) {
		S[cur]=S[pre]+(SA[0]-SA[cur])-SA[cur];
	}
	FORR(e,E[cur]) if(e!=pre) dfs2(e,cur);
}

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,-1,0);
	dfs2(0,-1);
	cout<<*max_element(S,S+N)<<endl;
}

まとめ

まだまだこのころは典型だね。