Abstract

There is a kind of Dynamic Programming (DP) where a tree is regarded as a subtree rooted at a vertex and the values are evaluated from leaves to root; it is called “tree DP” in the context of competitive programming. This problem is a kind of tree DP, where the \(\mathrm{dp}\) array is defined as follows:

• \(\mathrm{dp}_{i,j}\): the number of ways to choose whether \(V\) contains each vertex in the subtree rooted at vertex \(i\) which has \(j\) connected components.

Properties on the number of connected components in a forest

Before describing the detailed definition and transitions of actual \(\mathrm{dp}\), we describe the property of the number of connected components.
This time, any connected component of a induced subgraph is a tree; such a graph is called a forest. For any forest with \(n\) vertices, \(m\) vertices, and \(c\) connected components, \(c=n-m\) holds. Thus, when you decide whether to choose a vertex or not, the number of connected components is updated as follows:

• if the vertex is chosen, the number increases by \(1\) (because \(n\) increases by \(1\)).
• if two adjacent vertices are both chosen, the number decreases by \(1\) (because \(m\) increases by \(1\)).

Definition of \(\mathrm{dp}\)

We define \(\mathrm{dp}\) as follows:

• \(\mathrm{dp}_{i,j,k}\): the number of ways to choose whether \(V\) contains each vertex in the subtree rooted at vertex \(i\) which has \(j\) connected components, where vertex \(i\) is chosen if \(k=1\) and is not if \(k=0\).

Note the index \(k\) that represents whether vertex \(i\) chosen to take into account the transition of the number of connected components when adjacent vertices are both chosen.

Here is a naive transition: basically, the sum of children’s \(j\) (the number of connected components) maps to new \(j\). If vertex \(i\) is chosen, every occurrence of \(k=1\) decreases \(j\) by \(1\). For more details, see the sample code.

Complexity analysis

At a glance, evaluating \(\mathrm{dp}_{i,j,k}\) seems to cost \(\mathrm{O}(N^3)\) time because there are \(\mathrm{O}(N)\) values for \(i\) and \(j\), constant number of values for \(k\), and transition costs at worst \(\mathrm{O}(N)\) time. However, it can be sped up to sufficiently fast \(\mathrm{O}(N^2)\) time by not filling the table if \(j\) exceeds the number of vertices in the subtree rooted at vertex \(i\). (See also https://snuke.hatenablog.com/entry/2019/01/15/211812 (Japanese).) Such a tree DP is called “square-order tree DP.”

Sample code (C++)

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
using namespace std;

vector<vector<mint>> dfs(int c,int p,vector<vector<int>> &E){
	vector dp(2,vector<mint>(2,0));
	dp[0][0] = 1;
	dp[1][1] = 1;
	for(int i=0;i<E[c].size();i++){
		int to = E[c][i];
		if(to==p)continue;
		
		auto ret = dfs(to,c,E);
		vector ndp(2,vector<mint>(dp[0].size()+ret[0].size()-1,0));
		for(int j=0;j<dp[0].size();j++){
			for(int k=0;k<ret[0].size();k++){
				ndp[0][j+k] += dp[0][j] * (ret[0][k] + ret[1][k]);
				ndp[1][j+k] += dp[1][j] * ret[0][k];
				if(j+k>0)ndp[1][j+k-1] += dp[1][j] * ret[1][k];
			}
		}
		swap(dp,ndp);
	}
	return dp;
}

int main() {
    
	int N;
	cin>>N;
	
	vector<vector<int>> E(N);
	for(int i=0;i<N-1;i++){
		int a,b;
		cin>>a>>b;
		a--,b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	auto ret = dfs(0,-1,E);
	
	for(int i=1;i<=N;i++){
		cout<<(ret[0][i] + ret[1][i]).val()<<endl;
	}
	
	return 0;
}