给定一棵树,统计其子树数量。
一道小清新树形 DP 题。
定义 \(dp[i]\) 为 \(i\) 的子树数量,那么我们对于点 \(i\),进行 dfs 求出其子节点 \(v\),那么状态转移方程就是
\[dp[i]=\prod_{v}dp[v]
\]
吗?(
仔细想一想,还要考虑子树不选的方案,所以正确是:
\[dp[i]=\prod_{v}(dp[v]+1)
\]
最后的结果 \(ans=\sum\limits_{i=1}^{n}dp[i]\)。
555要是所有树形 DP 都这么返璞归真就好了(bushi
AC 代码:
//2021/8/16
#include <iostream>
#include <cstdio>
#define debug(c) cerr<<#c<<"="<<c<<endl
#define int long long
namespace Newstd
{
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<‘0‘ || ch>‘9‘)
{
if(ch==‘-‘)
{
f=-1;
}
ch=getchar();
}
while(ch>=‘0‘ && ch<=‘9‘)
{
x=x*10+ch-‘0‘;
ch=getchar();
}
return x*f;
}
inline void print(int x)
{
if(x<0)
{
putchar(‘-‘);
x=-x;
}
if(x>9)
{
print(x/10);
}
putchar(x%10+‘0‘);
}
}
using namespace Newstd;
using namespace std;
const int mod=1e9+7;
const int ma=100005;
struct Node
{
int v;
int nxt;
};
Node node[ma<<1];
int head[ma],dp[ma];//dp[i]:以 i 为根的子树数量
int idx;
inline void add(int u,int v)
{
node[++idx].v=v;
node[idx].nxt=head[u];
head[u]=idx;
}
inline void dfs(int u,int fath)
{
dp[u]=1;
for(register int i=head[u];i;i=node[i].nxt)
{
int v=node[i].v;
if(v!=fath)
{
dfs(v,u);
dp[u]=dp[u]*(dp[v]+1)%mod;
}
}
}
#undef int
int main(void)
{
#define int long long
int n;
n=read();
for(register int i=1;i<n;i++)
{
int u,v;
u=read(),v=read();
add(u,v);
add(v,u);
}
dfs(1,0);
int ans=0;
for(register int i=1;i<=n;i++)
{
ans+=dp[i];
ans%=mod;
}
printf("%lld\n",ans);
return 0;
}