C++14(g++5.4) 解法, 执行用时: 612ms, 内存消耗: 118104K, 提交时间: 2020-04-28 21:47:16

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,MOD=1e9+7;
typedef long long ll;
ll dp[N];
int n,x,y,head[N],edg[N<<1],net[N<<1],tot;
void add(int x,int y)
{
	edg[++tot]=y,net[tot]=head[x],head[x]=tot;
}
void dfs(int x,int f)
{
	dp[x]=1;
	ll res=0;
	for(int i=head[x];i;i=net[i])
	{
		int y=edg[i];
		if(y==f)continue;
		dfs(y,x);
		dp[x]*=(dp[y]+1);
		dp[x]%=MOD;
		res=(res+dp[y])%MOD;
	}
	dp[x]+=res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	cout<<(dp[1]+1)%MOD<<endl;
	return 0;
 } 

C++11(clang++ 3.9) 解法, 执行用时: 919ms, 内存消耗: 125924K, 提交时间: 2020-04-24 21:25:29

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int MAX_N=1010000;
const long long MOD=1e9+7;
long long dp[MAX_N];
vector<int>v[MAX_N];
void dfs(int x,int fa){
	int i;
	long long res=1;
	for(i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(y==fa)
		continue;
		dfs(y,x);
		dp[x]=(dp[x]+dp[y]-1+MOD)%MOD;
		res=res*dp[y]%MOD;
	}
	dp[x]=(dp[x]+1+res)%MOD;
}
int main(void){
	int n,i,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x); 
	}
	dfs(1,0);
	printf("%lld\n",dp[1]);
	return 0;
}