基准时间限制：1 秒 空间限制：131072 KB 分值: 20
B国拥有n个城市，其交通系统呈树状结构，即任意两个城市存在且仅存在一条交通线将其连接。A国是B国的敌国企图秘密发射导弹打击B国的交通线，现假设每条交通线都有50%的概率被炸毁，B国希望知道在被炸毁之后，剩下联通块的个数的期望是多少？
Input
一个数n（2<=n<=100000） 接下来n-1行，每行两个数x,y表示一条交通线。(1<=x,y<=n) 数据保证其交通系统构成一棵树。
Output
一行一个数，表示答案乘2^(n-1)后对1,000,000,007取模后的值。
Input示例
3 1 2 1 3
Output示例
8
分析：
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll mod=1000000007; 5 inline ll read() 6 { 7 ll x=0,f=1; 8 char ch=getchar(); 9 while(ch<'0'||ch>'9') 10 { 11 if(ch=='-') 12 f=-1; 13 ch=getchar(); 14 } 15 while(ch>='0'&&ch<='9') 16 { 17 x=x*10+ch-'0'; 18 ch=getchar(); 19 } 20 return x*f; 21 } 22 ll n,x,y; 23 ll a[100010]={0,1}; 24 ll qpow(ll x,ll p) 25 { 26 ll ret=1; 27 for(;p;p>>=1,x=x*x%mod) 28 { 29 if(p&1) 30 ret=ret*x%mod; 31 } 32 return ret; 33 } 34 int main() 35 { 36 n=read(); 37 ll ans=0; 38 for(int i=1;i<n;i++) 39 { 40 x=read(); 41 y=read(); 42 } 43 for(ll i=2;i<=100001;i++) 44 a[i]=2*a[i-1]+qpow(2,i-2),a[i]%=mod; 45 cout<<a[n]<<endl; 46 return 0; 47 }
