OI Problems   关于

#d6uqz2. Perfect Matchings

时间限制:1 s       空间限制:512 MiB       标签: 数学 组合数学 容斥原理 动态规划 树形动态规划 ICPC 辽宁 2021 缺题解 

算法难度等级:0       思维难度等级:0       实现难度等级:0

本题来源于:2021 年 ICPC 亚洲(辽宁)沈阳区域赛

给定 2n2n 个点的树,要求两两匹配。两个点能匹配当且仅当两点之间没有连边,问有多少种匹配方案。

n2000n\leq 2000

AAA gets a complete graph of 2n2n vertices, where every pair of distinct vertices is connected by a unique edge, as a birthday present. However, AAA thinks the complete graph is not that beautiful and he decides to delete 2n12n-1 edges that form a tree.

Now he wonders the number of different perfect matchings in the remaining graph. Note that a perfect matching is a set of nn edges where no two edges share a common vertex. Since the answer may be very large, you only need to output the answer modulo 998244353998\,244\,353.


The first line contains a single integer nn (2n2000)(2\le n\le 2\,000).

Each of the next 2n12n-1 lines contains two integers uu and vv (1u,v2n)(1\le u,v\le 2n), representing an edge deleted from the complete graph. It is guaranteed that the given edges form a tree of 2n2n vertices.


Output a line containing a single integer, representing the answer modulo 998244353998\,244\,353.


1 2
1 3
3 4
1 2
2 3
3 4
4 5
5 6