Codeforces Global Round 26 : E. Shuffle

コードは短いんだよな。
https://codeforces.com/contest/1984/problem/E

問題

木を成す無向グラフが与えられる。
この木Tに対し、シャッフルという操作を以下のように定義する。

• Tのうち根となる点vを一つ選ぶ。
• Tからvを削除し、残った各連結成分毎に再帰的にシャッフルを行う。
• 改めて、シャッフルした各連結成分の根とvを接続する。

木をシャッフルしたとき、葉の数を最大いくつにできるか。

解法

最初に選ぶ根を除くと、葉の数の最大値は残った要素の最大独立集合となる。
よって、全方位木DPの要領で、各点を根としたときの多要素の最大独立集合のサイズを求めればよい。

int T,N;
set<int> E[202020];
int dp[2][202020];
int ret;

void dfs(int cur,int pre) {
	dp[0][cur]=0;
	dp[1][cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		dp[0][cur]+=max(dp[0][e],dp[1][e]);
		dp[1][cur]+=dp[0][e];
	}
}

void dfs2(int cur,int pre,int d0,int d1) {
	dp[0][cur]+=max(d0,d1);
	dp[1][cur]+=d0;
	if(E[cur].size()==1) ret=max({ret,1+dp[0][cur],dp[1][cur]});
	FORR(e,E[cur]) if(e!=pre) {
		dfs2(e,cur,dp[0][cur]-max(dp[0][e],dp[1][e]),dp[1][cur]-dp[0][e]);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].insert(y-1);
			E[y-1].insert(x-1);
		}
		
		dfs(0,0);
		ret=0;
		dfs2(0,0,0,0);
		cout<<ret<<endl;
		
		
	}
}

まとめ

実装より考察パートがだいぶしんどい。