tijie
2026-10-12 22:32:14
发布于:广东
1阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;
const int MAXN = 2e5 + 10;
vector<int> g[MAXN];
int sz[MAXN];
ll ipow2[MAXN];
int n;
void dfs(int u, int fa)
{
sz[u] = 1;
for(int v : g[u])
{
if(v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
ipow2[0] = 1;
ll inv2 = 500000004;
for(int i=1;i<=n;i++)
{
ipow2[i] = ipow2[i-1] * inv2 % MOD;
}
for(int i=1;i<=n-1;i++)
{
int a,b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, -1);
ll ans = 0;
for(int u=1;u<=n;u++)
{
vector<int> comp;
for(int v:g[u])
{
if(sz[v] < sz[u]) comp.push_back(sz[v]);
else comp.push_back(n - sz[u]);
}
ll P0 = ipow2[n-1];
ll sum = 0;
for(int s : comp)
{
ll term = (1 - ipow2[s] + MOD) % MOD;
term = term * ipow2[(n-1)-s] % MOD;
sum = (sum + term) % MOD;
}
ll p = ( (1 - P0 + MOD) % MOD - sum + MOD ) % MOD;
ll contrib = p * inv2 % MOD;
ans = (ans + contrib) % MOD;
}
cout << ans << endl;
return 0;
}
这里空空如也

有帮助,赞一个