Codeforces #630 Div2 F. Independent Set

この回は不参加。
http://codeforces.com/contest/1332/problem/F

問題

木を成すグラフが与えられる。
このグラフの部分グラフにおける独立点集合は何通りか。

解法

各点は以下の3通りの選択肢がある。

• 点を取り除く
• 点は残すが独立点集合に含めない
• 点は残すし独立点集合に含める

あとはこれを葉からDPしていくだけ。

int N;
vector<int> E[303030];

const ll mo=998244353;
ll dp[303030][2][2];
// 0/1 selected
// 0/1 edge

void dfs(int cur,int pre) {
	dp[cur][0][0]=dp[cur][1][0]=1;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		ll to[2][2]={};
		int a,b,c,d,f;
		FOR(a,2) FOR(b,2) FOR(c,2) FOR(d,2) FOR(f,2) {
			if(f&&a&&c) continue;
			if(f==0 && c&&d==0) continue;
			(to[a][b|f]+=dp[cur][a][b]*dp[e][c][d])%=mo;
		}
		FOR(a,2) FOR(b,2) dp[cur][a][b]=to[a][b];
	}
}

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);
	cout<<(dp[0][0][0]+dp[0][0][1]+dp[0][1][1]+mo-1)%mo<<endl;
}

まとめ

Div2とはいえFにしては簡単？