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

https://atcoder.jp/contests/abc152/submissions/26075052