bzoj4455 & loj2091 [Zjoi2016]小星星 容斥原理+树形DP(+状压DP?)

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4455

https://loj.ac/problem/2091

题解

很不错的一道题。（不过在当时考场上应该是签到吧

有一种很显然是错的的树形 DP 方法：

令 \(dp[x][i]\) 表示树上 \(x\) 对于图上 \(i\) 这个点，然后转移的时候直接枚举 \(x\) 的孩子和 \(i\) 的孩子进行匹配。

这样显然会有很多重复配对（即树上的两个点配对图上同一个点）的。然后我就很快把这个算法给放弃了。

（应该多想想的；得到一个教训：想到一个假算法以后要看看有没有一个方法把这个算法给改成正确的

然后正解就非常妙了：因为既然会有重复配对，那么图上也一定会有没有被配对的点。所以可以考虑直接容斥一下有那些点没有被配对，这些点就是禁止选的了。

最终容斥完医护就可以得到正确答案了。

时间复杂度 \(O(2^nn^3)\)。

---

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {
    int f = 0, c;
    while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
    x = c & 15;
    while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
    f ? x = -x : 0;
}

const int N = 17 + 7;

int n, m, cnt;
ll ans;
int ban[N];
ll dp[N][N];
std::vector<int> g1[N], g2[N];

inline void dfs(int x, int fa = 0) {
    for (int i = 1; i <= n; ++i) dp[x][i] = !ban[i];
    int len = g2[x].size();
    for (int ii = 0, y; ii < len; ++ii) if (y = g2[x][ii], y != fa) {
        dfs(y, x);
        for (int i = 1; i <= n; ++i) if (!ban[i]) {
            int len = g1[i].size();
            ll sum = 0;
            for (int jj = 0, j; jj < len; ++jj) {
                j = g1[i][jj];
                sum += dp[y][j];
            }
            dp[x][i] = dp[x][i] * sum;
        }
    }
}

inline void calc() {
    dfs(1);
    ll sum = 0;
    for (int i = 1; i <= n; ++i) if (!ban[i]) sum += dp[1][i];
    if (cnt & 1) ans -= sum;
    else ans += sum;
}

inline void dfs1(int x) {
    if (x == n + 1) return calc();
    ban[x] = 0, dfs1(x + 1);
    ban[x] = 1, ++cnt, dfs1(x + 1), --cnt;
}

inline void work() {
    dfs1(1);
    printf("%lld\n", ans);
}

inline void init() {
    read(n), read(m);
    int x, y;
    for (int i = 1; i <= m; ++i) read(x), read(y), g1[x].pb(y), g1[y].pb(x);
    for (int i = 1; i < n; ++i) read(x), read(y), g2[x].pb(y), g2[y].pb(x);
}

int main() {
#ifdef hzhkk
    freopen("hkk.in", "r", stdin);
#endif
    init();
    work();
    fclose(stdin), fclose(stdout);
    return 0;
}