- $f[i][j]$:以i为根的子树,且i在原图中的映射为j时的方案数
- $f[i][j]=\prod{u\in i.child}\Sigma ^n {k=1} f[u][k]*map[i][u]$
- 但这样求出的dp值包括了不合法的重复选点状态。重复选了一个的,两个的……选了(1,2)的,(1,3)的……..
- 容斥的套路呼之欲出。
- 所以需要套用容斥定理,枚举删点方案dp。
- $ps.$其实列出柿子之后首先想到的应该是状压,多加一维表示子集转移。
1 |
|
Viva la Vida
1 | #include<cstdio> |