yukicoder : No.2214 Products on Tree

割とざっくりで通ってしまった。
https://yukicoder.me/problems/no/2214

問題

N頂点の木を成すグラフが与えられる。
ここから辺の取り除き方は2^(N-1)通り考えられる。
各取り除き方において、各連結成分の頂点数の積の和を答えよ。

解法

木DPで解く。
各頂点毎に、SubTreeにおける連結成分の頂点数の積和と、根頂点と非連結な頂点の積和を求め、それぞれ子頂点の計算結果を合わせていこう。

int N;
vector<int> E[202020];
const ll mo=998244353;

ll S[202020];
ll M[202020];


void dfs(int cur,int pre) {
	S[cur]=M[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		ll PS=S[cur];
		ll PM=M[cur];
		S[cur]=M[cur]=0;
		dfs(e,cur);
		//con
		(S[cur]+=PS*M[e]+PM*S[e])%=mo;
		(M[cur]+=PM*M[e])%=mo;
		//dis
		(S[cur]+=PS*S[e])%=mo;
		(M[cur]+=PM*S[e])%=mo;
	}
}

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<<S[0]<<endl;
		
}

まとめ

最初大体の式を書いて、後で合わせようと思ったら、大体の式の段階で当たってしまった。