AtCoder Beginner Contest 149 F - Surrounded Nodes

F - Surrounded Nodes

問題

$n$ 頂点の木が与えられる.

今からこの木の各頂点を,独立に確率 $\frac{1}{2}$ で黒か白に塗る. 塗り終わった後,黒い頂点を全て含む最小の部分木 $S$ を取る.

このとき, $S$ に含まれる白い頂点の個数の期待値を求めよ.

制約

  • $2 \leq n \leq 2 \times 10^5$

考察

期待値問題の常套手段として,代わりに $p_v =$ 「頂点 $v$ が白く塗られ,かつ $S$ に含まれる確率」を求めることにする.すると答えは $\sum p_v$ となる. ただ,ここでは $p_v$ の代わりに求めやすい「頂点 $v$ が白く塗られ,かつ $S$ に含まれない確率」を求めることにする.

木から頂点 $v$ を取り除くと,いくつかの部分木 $T_1, \cdots, T_k$ へと分解される.このとき「 $v$ が $S$ に含まれない」ことは,「 $T_1, \cdots, T_k$ のうち黒い頂点を含むものが 1 つ以下である」ことと同値となる。

黒い頂点を含む $T_i$ が 1 つもない確率は、全頂点が白である場合のみなので $2^{-n}$ .黒い頂点を含む $T_i$ がちょうど 1 つである確率は,各 $i$ について「 $T_i$ が黒い頂点を少なくとも 1 つ含み,他は全部白の確率」を足し上げればよく,これは

$$ \sum_{i=1}^{k} \frac{1}{2^{n - |T_i|}} \cdot \left(1 - \frac{1}{2^{|T_i|}} \right) $$

で求まる.

よって後は各 $v$ について $|T_1|, \cdots, |T_k|$ が求まればよく,これは DFS により全体で $O(n)$ で計算できる.

実装例

提出 #9227350 - AtCoder Beginner Contest 149

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <functional>

template <int MOD>
struct ModInt { ... };

template <class Cost = int>
struct Edge { ... };

template <class Cost = int>
using Graph = std::vector<std::vector<Edge<Cost>>>;

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

int main() {
    const mint twoinv = mint(2).inv();

    int n;
    std::cin >> n;

    Graph<> tree(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        tree[u].emplace_back(u, v);
        tree[v].emplace_back(v, u);
    }

    mint ans = 0;

    // vを根とする部分木のサイズを返す
    std::function<int(int, int)> dfs =
        [&](int v, int r) {
            std::vector<int> ch;
            int sz = 0;

            for (auto e : tree[v]) {
                if (e.dst == r) continue;
                ch.push_back(dfs(e.dst, v));
                sz += ch.back();
            }

            // rを含む部分木のサイズ
            ch.push_back(n - 1 - sz);

            mint co = twoinv.pow(n);  // 全部白
            for (auto c : ch) {
                // 1つだけ黒を含む
                co += twoinv.pow(n - c) * (mint(1) - twoinv.pow(c));
            }

            ans += twoinv - co;  // 余事象を取る
            return sz + 1;
        };

    dfs(0, -1);
    std::cout << ans << std::endl;
    return 0;
}
Built with Hugo
テーマ StackJimmy によって設計されています。