题解：P3349
Danslapiscine · · 题解
容斥在dp中的应用 经典题。
啊这题首先是要dp （因为其他想法都是难维护的难以达到正解）
设计状态，按照一般的树形 dp 去想，如何描述清楚一个子树的形态？我们需要知道在树上的根节点 i，在图上对应的点 j，和在图上对应的点集 S。然后发现每个节点的转移肯定是绕不开枚举子集的。
于是想改状态，对枚举子集的祸首点集 S 动刀。为什么需要维护 S？因为我们要使任意图上的点不同时在两个子树里发生匹配，也就是最终一个点不能匹配两次。由于是 n 与 n 的匹配，那么上等价于在最终的匹配中每一个图上的点都必须出现。
然后便可以看出这是一个容斥可解决的问题，只要求“最多有 i 个图上的点在匹配中出现，匹配的方案数”。于是我们事先钦定可选点集 S，然后 dp 维护匹配的过程，就做完了。