# ABC149-F Surrounded Nodes

https://atcoder.jp/contests/abc149/tasks/abc149_f

問題概要: 問題を読む

主客転倒、各頂点$0, 1, \dots, N - 1, N$について、その頂点が穴あき度に寄与するような(その頂点が$S$に含まれて、かつ自身が白色となる)$S$の通り数($e_v$)を考えます。

期待値の線形性より、$\frac{\sum_{i = 1}^{N}e_v}{2^N}$が解になります。

$e_v$の計算方法について、余事象を考えます。$v$が黒色の時は自明なので、白色の時(だけど、$S$に含まれないので穴あき度に寄与しない)数を数えたいです。

$S$が空グラフである時は当然$v$は$S$に含まれません。そうで無い時、($v$を根と仮定して)「$v$のちょうど一つの部分木に黒頂点が含まれており、他の部分木には黒頂点が含まれていない」です。このような色の塗り方は、部分木のサイズが求まっていれば簡単なdpで数えることができます。

以上より、部分木のサイズを「現在頂点$v$を見ている時、$v$を根とした上で子頂点の部分木のサイズが求まっている」ようにdfsで更新しながら(全方位木dp?)以上のdpを回して解に足せば良いです。

サイズの更新は、予め適当な頂点$r$を根とした各頂点の部分木のサイズを求めておいて、

dfs(int v, int p) {
    int origin = size[v];
    for (auto x : g[v]) if (x != v) {
        size[v] = n - size[x];
        dfs(x, v);
    }
    size[v] = origin;
}

とすればできます。お手軽。

### 実装

#include <bits/stdc++.h>

#include <atcoder/modint>
using mint = atcoder::modint1000000007;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n; std::cin >> n;
    std::vector g(n, std::vector<int>{});
    for (int _{} ; _ < n - 1 ; _++) {
        int u, v; std::cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    std::vector<int> sz(n);
    auto rec{[&](auto rec, int v, int p) -> int {
        sz[v] = 0;
        for (auto x : g[v]) if (x != p) {
            sz[v] += rec(rec, x, v);
        }
        sz[v]++;
        return sz[v];
    }};

    rec(rec, 0, -1);

    std::vector<mint> p2(n + 1, mint{1});
    for (int i{} ; i < n ; i++) p2[i + 1] = p2[i] * mint{2};

    mint ans{};
    auto rec2{[&](auto rec, int v, int p) -> void {
        mint val{p2[n - 1]};
        std::vector<mint> dp(2); 
        dp[0] = mint{1};
        for (auto x : g[v]) {
            std::vector<mint> nxt(2);
            nxt[0] = dp[0];
            nxt[1] = dp[1] + dp[0] * (p2[sz[x]] - 1);
            dp = std::move(nxt);
        }
        val -= dp[0] + dp[1];
        ans += val;
        int origin{sz[v]};
        for (auto x : g[v]) if (x != p) {
            sz[v] = n - sz[x];
            rec(rec, x, v);
            sz[v] = origin;
        }
    }};
    rec2(rec2, 0, -1);
    ans /= p2[n];

    std::cout << ans.val() << std::endl;
}

## 感想
立式等わりとスムーズにできた。OK