不错的题。
考虑题目等价于,每个点等概率选或不选,求导出子图大小减选出点数的期望。
考虑一个点在导出子图的充要条件,发现不好计算。正难则反,考虑不在导出子图的充要条件,其实就是,所有点都在 \(u\) 的一棵子树内,或者 \(u\) 子树内没有选点。那么我们得到点 \(u\) 在导出子图的概率是:
\[1 - \frac{2^{n - sz_u}}{2^n} - \sum\limits_{v \in son_v} \frac{2^{sz_v} - 1}{2^n}
\]
可以计算出导出子图大小的期望,选出点数的期望显然是 \(\frac{n}{2}\),减一下就是最终答案。
code
// Problem: F - Surrounded Nodes
// Contest: AtCoder - AtCoder Beginner Contest 149
// URL: https://atcoder.jp/contests/abc149/tasks/abc149_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 1000000007;
const ll inv2 = (mod + 1) / 2;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
int n, sz[maxn];
ll ans;
vector<int> G[maxn];
void dfs(int u, int fa) {
sz[u] = 1;
ans = (ans + 1) % mod;
for (int v : G[u]) {
if (v == fa) {
continue;
}
dfs(v, u);
ans = (ans - (qpow(2, sz[v]) + mod - 1) % mod * qpow(inv2, n) % mod + mod) % mod;
sz[u] += sz[v];
}
ans = (ans - qpow(2, n - sz[u]) * qpow(inv2, n) % mod + mod) % mod;
}
void solve() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
dfs(1, -1);
ans = (ans - inv2 * n % mod + mod) % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Surrounded Beginner AtCoder Contest Nodessurrounded beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 334 beginner atcoder contest 328 beginner atcoder contest 310