主要思路

怎么毫无头绪啊？（wtcl）不过有一说一，题目是真的挺好。

有一种接近正解的方式是设置 DP，设 \(dp[u][i][stat]\) 为当前在点 \(u\)、编号为 \(i\) 且被用过的编号集合为 \(stat\)，然后做一个树形 DP。不难分析出这个东西的复杂度是 \(\Theta(n^3 3^n)\)。

这个肯定过不了的，考虑进行玄学优化。假设转移时能去掉第三个限制就好了。我们考虑抛弃这个第三维。抛弃之后必须要面对的一个问题就是非法状态。我们可以考虑硬点一个点集，使得整个 DP 的时候只能选点集内的编号。发现这样答案的意义是至少有 \(i\) 个重叠选择的点的方案数，所以我们可以愉快的套一个 \((-1)^{n – |S|}\) 系数就可以的出恰好为 \(0\) 个重叠选择的方案数了。

代码

// P3349.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 20;

typedef long long ll;

int head[MAX_N], current, mp[MAX_N][MAX_N], col[MAX_N], siz, n, m;
ll dp[MAX_N][MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u);
    for (int i = 1; i <= siz; i++)
    {
        int cc = col[i];
        dp[u][cc] = 1;
        for (int j = head[u]; j != -1; j = edges[j].nxt)
            if (edges[j].to != fa)
            {
                ll sum = 0;
                for (int k = 1; k <= siz; k++)
                    sum += dp[edges[j].to][col[k]] * mp[cc][col[k]];
                dp[u][cc] *= sum;
            }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), mp[u][v] = mp[v][u] = 1;
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    ll ans = 0;
    for (int stat = 0; stat < (1 << n); stat++)
    {
        siz = 0;
        for (int i = 0; i < n; i++)
            if (stat & (1 << i))
                col[++siz] = i + 1;
        dfs(1, 0);
        ll pans = 0;
        for (int i = 1; i <= siz; i++)
            pans += dp[1][col[i]];
        ans += (((n - __builtin_popcount(stat)) & 1) ? -1LL : 1LL) * pans;
    }
    printf("%lld\n", ans);
    return 0;
}