yukicoder : No.2047 Path Factory

これは割と典型か。
https://yukicoder.me/problems/no/2047

問題

N頂点の木を成す無向グラフが与えられる。
いくつか辺を消すとき、その消し方は2^(N-1)通りである。
そのうち、各連結成分がパスとなるようなものは何通りか。

解法

木DPで解く。
現在見ている頂点が、

• 孤立点
• パスの端点
• パスの途中

のいずれであるかの状態ごとに、各子頂点との辺を残すか消すか見ていく。

最後に、親頂点側との辺を残す場合と消す場合の組み合わせの数を計算していこう。

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

void dfs(int cur,int pre) {
	ll from[3]={1,0,0};
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		ll to[3]={};
		to[0]=(from[0]*dp[e][0])%mo;
		to[1]=(from[1]*dp[e][0]+from[0]*dp[e][1])%mo;
		to[2]=(from[1]*dp[e][1]+from[2]*dp[e][0])%mo;
		swap(from,to);
	}
	
	dp[cur][0]=(from[1]+from[2])%mo;
	dp[cur][1]=(from[0]+from[1])%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);
	}
	
	if(N==2) {
		cout<<1<<endl;
		return;
	}
	FOR(i,N) if(E[i].size()>=2) {
		dfs(i,i);
		cout<<dp[i][0]<<endl;
		return;
	}
	
		
}

まとめ

典型っぽい気はするけど、初出なのかな？