【题解】[ZJOI2016] 小星星 容斥+树形 dp ——quhengyi11

传送喵 qwq

题意，给你一个有标号的图和有标号的树，求树上点一一映射到一个子图上的方案数

题解

首先我们来设方程，我们要有一个对应关系，所以我们设 $f[i][j]$表示树上的点 $i$映射到图上点 $j$的方案数，因为我们还要保持一一对应关系，我们还要记录一个当前图的点集 $s$当做第三维，枚举的新加入的点必须在 $s$的补集上面。这样的复杂度会 gg(尽管我似乎不太会证但是肯定是保守在 $3^{17}$以上的)

所以我们需要考虑容斥，其实你想到容斥之后就是套路了，你枚举图中可以被选择的点，然后不用管重复关系，树形 dp 就是 $O(n^3)$的，然后外面枚举图状态是 $O(2^n)$的，所以总复杂度是 $O(n^3 2^n)$

但是有一些卡常技巧需要注意

首先因为主要复杂度在树形 dp 的 $dfs$里面，我们要先枚举边集马上 $dfs$然后再转移否则飞 $T$到会起 (仿佛一个 GD 人说出了 HN 话)。

然后有一个毒瘤的事情

在第三层循环里面常数优化是十分毒瘤的

以下三段代码从慢到快

if (c[i][j] && !ban[i] && !ban[j])
    now += f[v][j];

(c[i][j] & !ban[i] & !ban[j]) ? now += f[v][j] : 19260817;

now += f[v][j] * (c[i][j] & !ban[i] & !ban[j]);

其中第一种比第二种快一点点 (实测是 15% 左右)，第三种比第二种快 2.5 倍左右

也就是说，如果你的 $if$语句里面只有一句话或者两句话，不妨直接把条件和表达式乘一下会更快呢 $qwq$

当然就这题而言你可以预处理一下当前子图的点集，也可以省去一大波常数

代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define Re register
#define N 20 
#define mod 1004535809
#define ll long long 
#define qwq
bool c[N][N], ban[N];
int head[N], n, m, tot;
ll ans;
struct edge{
    int nxt, v; 
}e[804]; 
inline void addedge (int u, int v)
{
    e[++tot] = (edge) {head[u], v};
    head[u] = tot; 
} 
ll f[N][N]; 
inline void dfs (int u, int fa)
{
    fo (i, 1, n)
    {
        if (ban[i]) {f[u][i] = 0; continue;} else f[u][i] = 1;
        edge (I, u)
        {
            if (v == fa) continue;
            dfs(v, u);
            ll now = 0; 
            fo (j, 1, n)
                if (c[i][j] && !ban[i] && !ban[j])
                    now += f[v][j];
            f[u][i] = f[u][i] * now;
        }
    }
} 
int main()
{
#ifdef debug 
    freopen("in.txt", "r", stdin); 
#endif 
    scanf("%d %d", &n, &m);
    fo (i, 1, m)
    {
        int u, v; 
        scanf("%d %d", &u, &v);
        c[u][v] = c[v][u] = 1; 
    }
    fo (i, 2, n) 
    {
        int u, v;
        scanf("%d %d", &u, &v);
        addedge(u, v);
        addedge(v, u); 
    }
    int up = (1 << n) - 1;
    fo (s, 0, up)
    {
        int cnt = 0;
        fo (i, 1, n) 
            if (1 << i - 1 & s)
                ban[i] = 1, ++cnt;
            else
                ban[i] = 0;
        dfs(1, 0);
        ll sum = 0;
        fo (i, 1, n) sum += f[1][i];
        if (cnt & 1) ans -= sum; else ans += sum;
    }
    printf("%lld", ans);
}