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;
}