Codeforces ECR #067 : E. Tree Painting

こっちの方が典型感あるね。
https://codeforces.com/contest/1187/problem/E

問題

木を成す無向グラフが与えられる。
各頂点は白く塗られている。
最初任意の頂点を1つ選んで黒く塗り、以後黒点に接する白点を選んで塗る。
点を塗るたび、その対象の白頂点だけで構成される連結成分の頂点数だけのスコアが入る。

最適な順で点を塗るとき、総スコアの最大値はいくらか。

解法

根付き木の根の頂点が塗られると、あとはそのSubTreeは塗る順番を問わず総スコアが確定する。
よって、全方位木DPの要領で、全頂点を最初の点とした場合のスコアを求めればよい。

int N;
vector<int> E[202020];
int C[202020];
ll SC[202020];
ll ma;
void dfs(int cur,int pre) {
	C[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		C[cur]+=C[e];
		SC[cur]+=SC[e];
	}
	SC[cur]+=C[cur];
}

void dfs2(int cur,int pre,ll sc) {
	SC[cur]+=N-C[cur]+sc;
	ma=max(ma,SC[cur]);
	FORR(e,E[cur]) if(e!=pre) {
		dfs2(e,cur,SC[cur]-SC[e]-C[e]);
	}
	
}

void solve() {
	int i,j,k,l,r,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);
	}
	
	dfs(0,0);
	dfs2(0,0,0);
	cout<<ma<<endl;
}

まとめ

まぁEducationalだしね。