题目链接

题意:给一个 n 个点 m 条边的无向图, 再给你一棵 n 个点的树,问有多少种点编号的映射方式,使得 n 个点恰好匹配,且树上的边均存在于原图中。


有一个错误的树形 dp 做法: \(dp_{i,j}\) 表示考虑以 i 为根的子树匹配完毕,其中根节点与 j 映射的方案数,可以简单的 \(O(n^3)\) 转移。

这么做显然可以满足树上的边都存在于原图中,但是并非所有点都被恰好使用一次,为了满足这个限制,枚举点集容斥即可。

答案即 没有点一定不被使用-有一个点一定不被使用+有两个点一定不被使用...

 


一个非常弱的准退役OIER