noip2019集训测试赛（六）B.匹配

本文主要是介绍noip2019集训测试赛（六）B.匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Rikka有一张无向联通图 G=⟨V,E⟩ ，其中顶点数 |V|=n ，边数 |E|=n−1 。Rikka可以选择 E 中的一些边删掉。显然这有 2n−1 种方案。

Rikka想知道，有多少种方案使得删边后残余图中的最大匹配数恰好为 m 的倍数。由于答案可能很大，请输出答案对 998244353 取模的余数。

边集 S 是图 G=⟨V,E⟩ 的匹配当且仅当 S 中任意两条边都不相邻（无公共顶点）。图 G 的最大匹配是指边数 |S| 最多的匹配。图 G 的最大匹配数为图 G 的最大匹配的边数 |S| 。

---

Input

第一行包含两个正整数 n,m ( $1\le n\le 5\times 10^4，1\le m\le 200$ )

接下来 n−1 行，每行包含两个整数 u,v ，表示 G 的边集。

---

Output

输出一个整数，表示答案对 998244353 取模的余数。

---

Solution

树形DP

下面转自https://www.cnblogs.com/FxxL/p/7351404.html。

记 $f[i][j]$表示，以i为根的子树的所有子图（包含子树所有节点，删掉一些边得到的子图）中，符合下列条件的子图的个数：

1. 记子图最大匹配为$h_1$,子图去掉与i节点相连的边后的最大匹配为$h_2$，满足 $h$

这篇关于noip2019集训测试赛（六）B.匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---