998244353">思路

998244353">设 $dp_u_i_0$表示 以点 u 为根的子树 最大匹配数模 m 为 i 时，且 u 点没有匹配的方案数

DP[u][i][1] 表示 以点 u 为根的子树 最大匹配数模 m 为 i 时，且 u 点匹配上的方案数

DP[u][k][0]（不匹配该节点） += 　　∑ [i+j==k] 2 * DP[u][i][0] * DP[v][j][1]（此时u->v这条边连不连都不会影响到匹配集，所以*2） + 　　DP[u][i][0] * DP[v][j][0]（儿子已近匹配了） DP[u][k][1]（该节点已经连了边） += 　　 ∑ [i+j==k] 2 * DP[u][i][1] * ( DP[v][j][0] + DP[v][j][1] ) DP[u][k][1] （该节点现在正要连边）+= 　　∑ [i+j==k-1（预留出一个位用于匹配）] DP[u][i][0] * DP[v][j][0]（此时这条边必须存在并且u，v都不能匹配别的边）

代码

#include
#include
#include
#include
using namespace std;
#define int long long
#define mod 998244353
#define N 50001
#define M 410
vector vec[N];
int dp[N][M][2],size[N]/*记录节点能最多能匹配多少边*/,temp[M][2]/*dp数组在更新中途不能更改，故用此数组代替*/,m;
void add(int u,int v)//使用边更新数组
{
    memset(temp,0,sizeof(temp));
    for(int i=0;i<=size[u];i++)//这里时间复杂度可以证明为n*m
    {
        for(int j=0;j<=size[v];j++)
        {
            temp[i+j][0]+=2*dp[u][i][0]*dp[v][j][1]+dp[u][i][0]*dp[v][j][0];
            temp[i+j][0]%=mod;
            temp[i+j][1]+=2*dp[u][i][1]*(dp[v][j][0]+dp[v][j][1]);
            temp[i+j][1]%=mod;
            temp[i+j+1][1]+=dp[u][i][0]*dp[v][j][0];
            temp[i+j+1][1]%=mod;
        }
    }
    for(int i=0;i>n>>m;
    for(int i=1;i