思路

树形dp,设计状态如下:

 

设 $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 410vector 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