基准时间限制：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代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
ll n,x,y;
ll a[]={,};
ll qpow(ll x,ll p)
{
ll ret=;
for(;p;p>>=,x=x*x%mod)
{
if(p&)
ret=ret*x%mod;
}
return ret;
}
int main()
{
n=read();
ll ans=;
for(int i=;i<n;i++)
{
x=read();
y=read();
}
for(ll i=;i<=;i++)
a[i]=*a[i-]+qpow(,i-),a[i]%=mod;
cout<<a[n]<<endl;
return ;
}