题目描述

Facer是一个萌萌哒的码农

他写了N个程序

程序之间是有 有机的联系的

任意两个程序恰好由1条联系链连在一起

具体来说，对于程序a,b ， 存在且仅存在一个序列a,x1,x2....xn,b

使得a,x1有联系,x1,x2有联系.....

符合这样的一组程序称为程序块

现在已知一个程序块的程序之间的联系

询问它有多少个子程序块

即取出一个程序子集S，使得S也满足上述条件

输入输出格式

输入格式：

 

第一行N

接下来N-1行，每行两个数，代表有联系的两个程序

 

输出格式：

 

输出有多少个子程序块

对1000000007取模

 

输入输出样例

输入样例#1： 

31 22 3

输出样例#1： 

6

说明

样例解释：

子集(1),(2),(3),(1,2),(2,3),(1,2,3)满足

对于 10%的数据 1 <= N <= 20

对于 40%的数据 1 <= N <= 500

对于 100%的数据 1 <= N <= 100000

#include
     
      #define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)using namespace std;const int maxn=2e6+666;template 
      
       inline void rd(T &ret){    char c;    ret = 0;    while ((c = getchar()) < '0' || c > '9');    while (c >= '0' && c <= '9'){        ret = ret * 10 + (c - '0'), c = getchar();    }}const int mod=1e9+7;int head[maxn],tot;long long dp[maxn][2];struct node{       int u,v,nx;}p[maxn];void addedge(int u,int v){     p[++tot].v=v,p[tot].nx=head[u],head[u]=tot;}void dfs(int u,int fa){     dp[u][1]=1;     for(int i=head[u];i;i=p[i].nx){          int to=p[i].v;          if(to==fa)continue;          dfs(to,u);          dp[u][0]=(dp[u][0]+dp[to][1]+dp[to][0])%mod;          dp[u][1]=dp[u][1]*(1+dp[to][1])%mod;     }}int main(){    int n;    rd(n);    REP(i,1,n-1){         int x,y;         rd(x),rd(y);         addedge(x,y),addedge(y,x);    }    dfs(1,0);    cout<<(dp[1][0]+dp[1][1])%mod<