「LOJ2091」「ZJOI2016」小星星容斥+DP

题目描述

小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有\(n\)颗小星星，用 \(m\)条彩色的细线串了起来，每条细线连着两颗小星星。有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了\(n-1\)条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢。

输入

第一行包含两个正整数\(n,m\)，表示原来的饰品中小星星的个数和细线的条数。

接下来\(n-1\)行，每行包含两个正整数\(u,v\)，表示原来的饰品中小星星\(u\)和 \(v\)通过细线连了起来。

这里的小星星从开始标号。保证，且每对a小星星之间最多只有一条细线相连。接下来行，每行包含两个正整数，表示现在的饰品中小星星和通过细线连了起来。保证这些小星星通过细线可以串在一起。

输出

输出共一行，包含一个整数表示可能的对应方式的数量。

如果不存在可行的对应方式则输出\(0\)。

样例

样例输入

样例输出

数据范围

对于所有的数据\(n\leq 17\)，\(m\leq \frac{n(n-1)}{2}\)。

题解

首先，我诈尸了。

第二，这是道容斥原理好题目……

考虑这个问题的等价形式，对树上的点进行重标号，让重标号的点可以嵌入原图（即，树上相邻的点在原图也相邻），并且满足每个点不会有相同的编号，然后问重标号的方案数。

于是一个简单的状压\(DP\)就呼之欲出了：\(f[i][s]\)表示以\(i\)为根的子树，把\(s\)里的数全都标号了，方案数是多少？这个可以很容易地使用子集转移做到\(O(n^k3^n)\)，\(k\)随你实现的方法有所变化，然而不管\(k\)取多少都没办法过……毕竟有一个\(3^n\)在那里。

我们似乎没有办法了，不如考虑没有“两个点的标号不能相同”这个限制，这就非常好做了，\(f[i][j]\)表示以\(i\)为根的子树的答案，并且\(i\)的标号是\(j\)的方案。状态转移方程式显然很好写：

\[f[i][j]=\prod_{s\in son_i}\left(\sum_{A_{k,j}=1}f[s][k]\right)
\]

然后这个东西显然会求出重复标号，我们稍微想想就知道可以容斥出来答案。\(2^n\)枚举一下哪些点不能被使用，奇数个就减掉，偶数个就加上，感性理解一下看起来是对的。很显然，强制要求一些点不选并不会增加\(DP\)难度，复杂度大约是\(O(n^32^n)\)，我是不知道怎么继续优化了……用一些优化方式可以剪掉一些不必要的情况，卡卡常就过了。

\(Code:\)

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 20

#define ll long long

int n, m, A[N][N];

int tar[N << 1], nex[N << 1], fir[N], cnt;

ll f[N][N];

vector<int> ver[N];

void Add(int a, int b)

{

    ++cnt;

    tar[cnt] = b;

    nex[cnt] = fir[a];

    fir[a] = cnt;

}

void Dfs(int r, int fa, int s)

{

    for (int i = fir[r]; i; i = nex[i])

    {

        int v = tar[i];

        if (v != fa)

            Dfs(v, r, s);

    }

    for (int i = 1; i <= n; i++)

    {

        if (s & (1 << (i - 1)))

            continue;

        f[r][i] = 1;

        for (int j = fir[r]; j; j = nex[j])

        {

            int v = tar[j];

            if (v != fa) {

                ll sum = 0;

                int t = ver[i].size();

                for (int k = 0; k < t; k++)

                {

                    int p = ver[i][k];

                    if (s & (1 << (p - 1)))

                        continue;

                    sum += f[v][p];

                }

                f[r][i] *= sum;

            }

        }

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++)

    {

        int a, b;

        scanf("%d%d", &a, &b);

        ver[a].push_back(b);

        ver[b].push_back(a);

    }

    for (int i = 1; i < n; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        Add(u, v), Add(v, u);

    }

    ll ans = 0;

    for (int i = 0; i < (1 << n); i++)

    {

        Dfs(1, 0, i);

        ll sum = 0;

        int bit = 1;

        for (int j = 1; j <= n; j++)

            if (i & (1 << (j - 1)))

                bit = -bit;

            else

                sum += f[1][j];

        ans += bit * sum;

    }

    printf("%lld\n", ans);

}

小星星