树形DP入门求调
查看原帖
树形DP入门求调
333800
qip101楼主2022/7/29 09:39
//统计树的子树数量
#include <bits/stdc++.h> 
#define MOD 1000000007
#define MAXN 100100
using namespace std;
long long N,ans,dp[MAXN];//dp[u]表示以u为根节点的子树个数
//dp[u]=∏(dp[v]+1) (v=son(u))
vector <int> G[MAXN];
inline void add(int x,int y)
{
	G[x].push_back(y);
	G[y].push_back(x);
}
inline void dfs(long long x,long long fa)
{
	dp[x]=1;
	for(int i=0;i<G[x].size();i++)
	{
		if(G[x][i]!=fa)
		{
			dfs(G[x][i],fa);
			dp[x]=(dp[x]*dp[G[x][i]]+dp[x])%MOD;
		}
	}
	ans+=dp[x];
	ans%=MOD;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> N;
	for(int i=1;i<=N-1;i++)
	{
		long long a,b;
		cin >> a >> b;
		add(a,b);
	}
	dfs(1,0);
	cout << ans << endl;
	return 0;
}
2022/7/29 09:39
加载中...