ABC149 F - Surrounded Nodes
問題
考察
$ E(Sに含まれる白い頂点の個数)
$ = E(Sの頂点数 - 黒い頂点の個数)
$ = E(Sの頂点数) - E(黒い頂点数)
$ = E(Sの頂点数) - \frac{N}{2}
$ Sをとってから頂点を数えるのではなく、ある頂点が$ Sに含まれる回数を数えます。
$ E(Sの頂点数)
$ = \frac{1}{2^N} \sum_{Sのとり方} \sum_v x_{S,v}
$ x_{S,v}は$ vが$ Sに含まれるとき1、そうでないとき0
$ = \frac{1}{2^N} \sum_v \sum_{Sのとり方} x_{S,v}
頂点$ uが$ Sにふくまれる回数を$ n_uとします。$ uが$ Sに含まれるのは、$ uを取り除いてできる部分木$ T_{u1}, T_{u2}, \dotsのうち少なくとも2つに黒い頂点を含むときです。したがって、
$ n_u = 2^{N-1} - 1 - \sum_v(2^{|T_{uv}|} - 1)
すべて - 全部白 - $ T_{uv}のうち1つだけに黒が少なくとも1つあり他は白
となります。
$ E(Sの頂点数) = \frac{1}{2^N} \sum_u n_u = \frac{1}{2^N}(N(2^{N-1}-1) - \sum_u \sum_v(2^{|T_{uv}|} - 1) )
部分木の頂点数はDFSで数えることができます。ウニグラフのような、次数が高い頂点がある場合には注意が必要です。$ uを除いたときの$ vを含む木の大きさを$ (u,v)をキーとしてメモすると、空間としては$ 2Eですが、次数分の和が発生しうるので最悪時間計算量が$ O(N^2)になってしまいます。 https://gyazo.com/55096564ddeeb1251287430fa822d847
和をメモしておく方法もありますが、この問題の場合特に$ |T_{vu}| = N - |T_{uv}|なので$ O(N)にできます。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N;
vector<vector<int>> G;
unordered_map<int, unordered_map<int, int>> memo;
int count(int p, int u) {
if (memopu != 0) return memopu; if (memoup != 0) return N - memoup; int res = 1;
if (v == p) continue;
res += count(u, v);
}
}
int main() {
cin >> N;
G.resize(N);
rep(i, N - 1) {
int A, B;
cin >> A >> B;
--A, --B;
}
ModInt ans = (ModInt(2).pow(N - 1) - 1) * N;
rep(u, N) {
ans -= ModInt(2).pow(count(u, v)) - 1;
}
}
ans /= ModInt(2).pow(N);
cout << ans << endl;
return 0;
}