D 小红的树上移动
记忆化搜索
#include <bits/stdc++.h>
using namespace std;
#define R register
#define int long long
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int f[N];
int q_pow(int x, int a)
{
int sum = 1;
while(a)
{
if(a & 1) (sum *= x) %= mod;
(x *= x) %= mod;
a >>= 1;
}
return sum;
}
int niyuan(int x)
{
return q_pow(x,mod-2);
}
void dp(int x, int par, vector<vector<int>>& vrr)
{
if(vrr[x].size() == 1 && vrr[x][0] == par) // 叶子节点
{
f[x] = 1;
return;
}
int fz = 0, fm = 0;
for(R int i = 0; i < vrr[x].size(); ++ i)
{
int now_node = vrr[x][i];
if(now_node == par) continue;
else ++ fm;
if(f[now_node] == 0) dp(now_node,x,vrr);
(fz += f[now_node]) %= mod;
}
f[x] = (1 + fz * niyuan(fm)) % mod;
}
signed main()
{
int n;
cin >> n;
vector<vector<int>> vrr(n + 1);
for(R int i = 1; i <= n - 1; ++ i)
{
int u, v;
scanf("%lld%lld",&u,&v);
vrr[u].push_back(v);
vrr[v].push_back(u);
}
dp(1, -1, vrr);
cout << f[1];
return 0;
}