青岛响应式网站,个人可以做电商网站吗,山西省网站备案,上海网站建设q.479185700棒传送门
题目描述#xff1a;
有一张无向联通图 G⟨V,E⟩ #xff0c;其中顶点数 |V|n #xff0c;边数 |E|n−1 。求有多少种方案使得删边后残余图中的最大匹配数恰好为 m 的倍数。
题解#xff1a;
这道题看起来是求最大匹配#xff0c;其实关系不大#xff0c;正解…传送门
题目描述
有一张无向联通图 G⟨V,E⟩ 其中顶点数 |V|n 边数 |E|n−1 。求有多少种方案使得删边后残余图中的最大匹配数恰好为 m 的倍数。
题解
这道题看起来是求最大匹配其实关系不大正解是树形DP
定义一个数组dp[i][j][k], 其中
i表示节点
j表示i的子树中的最大匹配数%m
k表示i是否与其子节点匹配.
接下来推一下合并两颗子树uv的递推式即可
注意几个细节
1.用快读否则会TLE
2.尽量少取余否则会很慢
3.有2n条边我一开始就因为数组开小了卡了很久
4.dp[i][j][k]上一次的结果不带入这一次要另开一个tmp数组来执行操作
#includeiostream
#includecstdio
using namespace std;
typedef long long ll;
inline int read(){int x0,f1;char chgetchar();while(!isdigit(ch)){if(ch-)f-1;chgetchar();}while(isdigit(ch)){xx*10ch-0;chgetchar();} return x*f;
}
const int N50010;
const int M200;
const int mod998244353;
int n,m;
struct Edge{int v,nxt;
}edge[N1];
ll dp[N][M][2],tmp[M][2];
int head[N],cnt,fa[N],sz[N];
void add_edge(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void dfs(int u){sz[u]1;dp[u][0][0]1;for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vfa[u]) continue;fa[v]u;dfs(v);for(int i0;im;i) tmp[i][0]tmp[i][1]0;for(int j0;jsz[u]jm;j){for(int k0;ksz[v]km;k){int v1(jk1)%m,v2(jk)%m;tmp[v1][1]dp[u][j][0]*dp[v][k][0];tmp[v1][1]%mod;tmp[v2][0]dp[u][j][0]*dp[v][k][0]dp[u][j][0]*dp[v][k][1]*2;tmp[v2][0]%mod;tmp[v2][1]dp[u][j][1]*dp[v][k][0]*2dp[u][j][1]*dp[v][k][1]*2;tmp[v2][1]%mod;}}for(int i0;im;i){dp[u][i][0]tmp[i][0];dp[u][i][1]tmp[i][1];}sz[u]sz[v];}
}
int main(){nread();mread();for(int i1;in;i){int uread();int vread();add_edge(u,v);add_edge(v,u);}dfs(1);printf(%d\n,(dp[1][0][0]dp[1][0][1])%mod);return 0;
}
