【题解】bzoj4455/洛谷 P3349 小星星 容斥+树形 DP ——litble

有大佬曰过，像这种全排列计数类的问题，常常是子集 DP。
也就是可以考虑，对于树上每一个节点 x，它所在的子树，在图上的映射集合是 s，并且 x 对应着图上的点 i 的状态 f(x,i,s)，进行 DP。
这样复杂度还是太高。
发现复杂度瓶颈是在枚举子树的映射集合那里，而之所以要这么做，是因为树上点和图上点之间是一一映射。而假设映射不要一一对应，算出方案后，通过缩小映射集合进行容斥的方法是一个套路（虽然我这个蒟蒻是才知道这东西是套路），所以考虑容斥。
记 f(x,i) 表示树上点 x 对应图上点 i，其子树的映射方案数。这东西的 dp 是 $O(n^3)$的。
可能不是一一映射，也就是会有图上点对应不到树上点，那么就枚举并删掉那个没有被对应到的图上点，继续 dp 后从答案中减去。当然这样也会多算有两个图上点对应不到的情况，又要加上。然后还要减去有四个点对应不上的情况……
总之，复杂度是 $O(n^3 2^n)$的，不过，每次 DP 考虑的图上点往往达不到 $O(n)$级别…… 所以，这个复杂度也达不到这么大，具体是多少我太菜了算不出…… 就这样。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
int n,m,tot,js;LL ans;
int h[20],ne[40],to[40],l[20][20],bin[20],p[20];LL f[20][20];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dp(int x,int las) {
    for(RI i=1;i<=js;++i) f[x][p[i]]=1;
    for(RI i=h[x];i;i=ne[i]) {
        if(to[i]==las) continue;
        dp(to[i],x);
        for(RI j=1;j<=js;++j) {
            LL res=0;
            for(RI k=1;k<=js;++k)
                if(l[p[j]][p[k]]) res+=f[to[i]][p[k]];
            f[x][p[j]]*=res;
        }
    }
}
int main()
{
    int x,y;
    scanf("%d%d",&n,&m);
    for(RI i=1;i<=m;++i) scanf("%d%d",&x,&y),l[x][y]=l[y][x]=1;
    for(RI i=1;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    bin[1]=1;for(RI i=2;i<=n+1;++i) bin[i]=bin[i-1]<<1;
    for(RI zt=1;zt<bin[n+1];++zt) {
        js=0;
        for(RI i=1;i<=n;++i)
            if(zt&bin[i]) p[++js]=i;
        dp(1,0);LL res=0;
        for(RI i=1;i<=js;++i) res+=f[1][p[i]];
        if((js&1)==(n&1)) ans+=res;
        else ans-=res;
    }
    printf("%lld\n",ans);
    return 0;
}