牛客周赛62 小红的树上移动
作者:
Air1222
,
2024-09-30 14:21:07
,
所有人可见
,
阅读 2
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e5+10,MOD = 1e9+7;
vector<int>g[N];
long long dp[N];//统计到达每个点的期望
//ans=到达叶子节点染红的个数*dp[叶子节点]
//逆元qmi(x,MOD-2)
//没有特殊说明都为无向边
//注意1没有父节点
int n;
long long ans;
long long x,y;
LL qmi(int a,int b){
LL res=1%MOD;
while(b){
if(b&1)res=res*a%MOD;
a=a*(LL)a%MOD;
b>>=1;
}
return res;
}
void dfs(int u,int father,long long sum)
{
bool flag=false;
for(auto k:g[u])
{
if(k==father) continue;
flag=true;
dp[k]=(dp[u]%MOD*qmi(g[u].size()-(u!=1),MOD-2))%MOD;
//cout<<k<<" "<<u<<" "<<dp[k]<<" "<<dp[u]<<" "<<g[u].size()<<endl;
dfs(k,u,sum+1);
}
if(!flag)
ans+=(sum%MOD*dp[u])%MOD;
}
int main()
{
//cout<<qmi(1,MOD-2)<<endl;
cin>>n;
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dp[1]=1;
dfs(1,-1,1);
cout<<ans%MOD;
}