Tree and Constraints [AtCoder Beginner Contest 152 F]

https://atcoder.jp/contests/abc152/tasks/abc152_f

前提知識

• 包除原理

解説

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

条件の弱い所を探すと、N=50, M=20である。
N=50はまあまあ見るのでいいとして、M=20がどう見ても不自然。
ここから考え出す。
20というと、2²⁰が通るなという感じであり、数え上げで、満たすべき制約について…
包除原理である。

包除原理を用いると答えは以下のように求めることができる。
(制約を最低0個満たしていない)-(制約を最低1個満たしていない)+(制約を最低2個満たしていない)-...
これで計算する方針で考えよう。
2^Mで制約を満たす満たさないの全パターンを見て、組み合わせを計算し、引くか足すかしていく。

あるmskの集合の制約は満たさないと考えると、その集合に含まれる経路は全部白にする必要がある。
それで、それ以外の部分は何色でもいいので、適当に塗る組み合わせを考える。
これで、集合の個数がcntであるとすると、「制約を最低cnt個満たしていない」組み合わせが得られる。
その集合に含まれる経路に使われる辺の個数をwhite.countとすると、全部でN-1本なので、
rest(=N-1-white.count)本がどっちでも塗れる。
なので、組み合わせは2^rest通り。

最後に残ったのは、その集合に含まれる経路の辺の本数をどう数えるかである。
自分は元々ライブラリ化してあるLCAを使って木上を移動するやつを使った。
なくても、前計算できるので、dfsとかで最短経路を見つけて、戻りながら辺を集計すればできそう。
どの辺を使ったかをこちらも集合で記録しておこう。
pre[i] := i番目の制約で使用する辺の集合
これを用意しておくことで、ある集合に含まれる経路の辺集合は、集合のpreのOR和となるので便利。
50なのでllでもいいが、bitsetだとカウントできるからこっちを自分は使った。

色々前計算しないとTLEするので注意。

int N, M;
ll po[51];
bitset<50> pre[20];
//---------------------------------------------------------------------------------------------------
void _main() {
    po[0] = 1;
    rep(i, 1, 51) po[i] = po[i - 1] * 2;

    cin >> N;
    HLDecomposition hld(N);
    rep(i, 0, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        hld.add(a, b);
    }
    hld.build(0);

    cin >> M;
    rep(i, 0, M) {
        int u, v;
        cin >> u >> v;
        u--; v--;

        while (u != v) {
            int to = hld.go(u, v, 1);

            if(hld.depth[u] > hld.depth[to]) pre[i].set(u);
            else pre[i].set(to);
            
            u = to;
        }
    }

    ll ans = 0;
    rep(msk, 0, 1 << M) {
        int p = __builtin_popcount(msk) % 2;
        
        bitset<50> white;
        rep(i, 0, M) if (msk & (1 << i)) white |= pre[i];

        int rest = N - 1 - white.count();
        if (p == 0) ans += po[rest];
        else ans -= po[rest];
    }
    cout << ans << endl;
}