本文主要是介绍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 ≤ n ≤ 5 × 1 0 4 ， 1 ≤ m ≤ 200 1≤n≤5×10^4，1≤m≤200 1≤n≤5×104，1≤m≤200 )
接下来 n−1 行，每行包含两个整数 u,v ，表示 G 的边集。
Output
输出一个整数，表示答案对 998244353 取模的余数。
Solution
树形DP
下面转自https://www.cnblogs.com/FxxL/p/7351404.html。
记 f [ i ] [ j ] f[i][j] f[i][j]表示，以i为根的子树的所有子图（包含子树所有节点，删掉一些边得到的子图）中，符合下列条件的子图的个数：
- 记子图最大匹配为 h 1 h_1 h1,子图去掉与i节点相连的边后的最大匹配为 h 2 h_2 h2，满足 h 1 − h 2 = 0 h_1-h_2=0 h
这篇关于noip2019集训测试赛（六）B.匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
