F - Tree and Constraints
[Q] https://atcoder.jp/contests/abc152/tasks/abc152_f
・1<<33はオーバーフローで壊れてしまう。1はint型だ。
1LL<<33でlonglongとしておさまる。
・M=20に気づく。O(2^20)でbitDP。
問題文を逆にとらえ、2^(N-1)通りから、指定区間を全部白に塗った場合を引いていく。
N=50なので2^50と思いきや、辺の数M=20なので、2^20の幇助原理でいけると気づく。
Q. ほうじょ原理？
A.
辺が3つあるとする。辺1と2を白にしてはいけない塗り方は何通り？を考える。
すべての塗り方は2^3=8通り。
・1の辺を白と固定すると、
123
WBB
WBW
WWB
WBB
の4通りが濡れる。
・また、2の辺を白と固定すると、
123
BWB
BWW
WWB
WWW
の4通りが濡れる。
・これは、1,2を白に塗る
WWB
WWW
の2通りが重複している。
(4+4)-2=6通りが、1または2を白塗りする組み合わせなので、
8-6=2通りが正解。
all
- (1を白に塗る) - (2を白に塗る) // 選んだ要素が1つなのでマイナス
+ (1,2を白に塗る) // 選んだ要素が2つなのでプラス
選んだ要素が奇数の場合マイナス、偶数ならプラスすればつじつまが合う。実装。
vector<pll> G[55]; // G[今頂点] = {行先頂点, 辺id}
ll mhash[22]; // Mが通る辺をhash化
ll H[55][55]; // H[頂点a][頂点b] = a-bが通る辺のhash
void dfs(ll u, ll p, ll s, ll hash){ // {現在頂点, 1個前, スタート地点, 辺のhash値}
ll nhash;
for(auto v: G[u]){
ll nv=v.first;
if (nv == p) continue;
ll id=v.second;
nhash = hash|(1LL<<id);
H[s][nv] = nhash;
dfs(nv, u, s, nhash);
}
}
int main(){
cincout();
ll N;
cin >> N;
rep(i, N-1){
ll a, b;
cin >> a >> b;
--a, --b;
G[a].push_back({b, i});
G[b].push_back({a, i});
}
ll M;
cin >> M;
// グラフHの下準備。頂点間がどの辺を通るか、hashで入れる。
rep(i, N) dfs(i, -1, i, 0); // {現在頂点, 1個前, スタート地点, 辺のhash値}
rep(i, M){
ll u, v;
cin >> u >> v;
--u, --v;
mhash[i] = H[u][v];
}
ll ans = 0;
rep(i, (1<<M)){
ll thash = 0;
rep(j, M){
if ( ((i>>j)&1) == 0 ) continue;
thash |= mhash[j]; // 0が自由。1を全部白と仮定したNGな塗り方
}
ll black = (N-1) - __builtin_popcountll(thash);
if (__builtin_popcountll(i)%2 == 0) ans += (1LL<<black); // ほう助原理
else ans -= (1LL<<black);
}
cout << ans << endl;
}
Q. 18WAが抜けない
A. bit演算でオーバーフローしてるかも。1LL<<49する。
入力例
50
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21