自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 21:41:43，当前版本为作者最后更新于2019-07-11 12:58:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$Solution:$

定义:以$1$号节点为根

定义:$f[i]$为以节点$i$为根的子树个数

边界:$f[i]=1\ \ \ \ \ \ (\text{节点i为叶子节点}$

转移:$\large{}f[i]=\Large\prod\limits_{j\text{是i的子节点}}(f[j]+1)$

推理:对于状态$f[i],i$节点自身一定是要选的，而对于它的子节点为根的子树，有$f[j]$种方案，显然这颗子树也可以不选，所以有$(f[j]+1)$种选法，根据乘法原理，总方案数为它们的乘积，即$\prod\limits_{}(f[j]+1)$

答案:$\sum\limits_{i=1}^nf[i]$

$Code:$

#include<bits/stdc++.h>
#define p 1000000007
using namespace std;
typedef long long ll;
int n,h[100005],tot=0;
struct edge{
	int to,next;
}e[200005];
void add(int x,int y){
	e[++tot].to=y;e[tot].next=h[x];h[x]=tot;
}
int f[100005],ans=0;
void dfs(int x,int fa){
	f[x]=1;
	for(int i=h[x];i;i=e[i].next)
	  if(e[i].to!=fa)
	    dfs(e[i].to,x),f[x]=(ll)((ll)f[x]*f[e[i].to]+f[x])%p;
	ans+=f[x];ans%=p;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);
	}
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}