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×104，1≤m≤200 )
接下来 n−1 行，每行包含两个整数 u,v ，表示 G 的边集。
Output
输出一个整数，表示答案对 998244353 取模的余数。
Solution
树形DP
下面转自https://www.cnblogs.com/FxxL/p/7351404.html。
记 f[i][j]表示，以i为根的子树的所有子图（包含子树所有节点，删掉一些边得到的子图）中，符合下列条件的子图的个数：
- 记子图最大匹配为h1,子图去掉与i节点相连的边后的最大匹配为h2，满足 h1−h2=0
- h1 % m=j
记g[i][j]表示，以i为根的子树的所有子图（包含子树所有节点，删掉一些边得到的子图）中，符合下列条件的子图的个数：
- 记子图最大匹配为h1,子图去掉与i节点相连的边后的最大匹配为h2，满足 h1−h2=1
- h1 % m=j
则对于每个根节点 p 遍历其后继，回溯计算答案，当遍历到后继 q 时，有下列递推式成立
下面是我对此的理解：
- 第一条是q连p可以，q连已有的后继也可以，所以乘二
- 第二条是p连q可以，p连已有的后继也可以，所以乘二（其实与第一条没区别）
- 第三条是一定会有p连q的边来保证去掉p使得最大匹配数减一
- 第四条是一定没有p连q的边来保证去掉p使得最大匹配数不变
- 第五条是p连q可以，不连也可以，所以乘二
如果有不同意见或我有错误可以评论@我，欢迎吊打(雾
Code
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
vector<int>v[50010];
int n,m,g[50010][210];
int f[50010][210],siz[100010];
int F[410],G[410];
void work(int x,int y){
memset(F,0,sizeof(F));//暂时保存数组
memset(G,0,sizeof(G));
for(int i=0;i<=siz[x];i++)
for(int j=0;j<=siz[y];j++){
G[i+j]=(G[i+j]+2ll*g[x][i]*g[y][j]+2ll*g[x][i]*f[y][j])%mod;
G[i+j+1]=(G[i+j+1]+1ll*f[x][i]*f[y][j])%mod;
F[i+j]=(F[i+j]+1ll*f[x][i]*f[y][j]+2ll*f[x][i]*g[y][j])%mod;
}
for(int i=0;i<m;i++){//只要算出0~2*(m-1)就好了，因为最小是0+0=0，最大是(m-1)+(m-1)=2*(m-1)
f[x][i]=(F[i]+F[i+m]+0ll)%mod;//模数相同加起来
g[x][i]=(G[i]+G[i+m]+0ll)%mod;
}
siz[x]=min(siz[x]+siz[y],m-1);//一个一个儿子加进父亲的siz中
}
void dfs(int u,int fa){
f[u][0]=1;
for(int i=0;i<v[u].size();i++)
if(v[u][i]!=fa){
dfs(v[u][i],u);
work(u,v[u][i]);
}
siz[u]=min(m-1,siz[u]+1);//大于m没有什么用，我们只算%m的余数
}
int main(){
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,-1);
printf("%d",(g[1][0]+f[1][0]+0ll)%mod);//将两种情况加起来就是答案
}