Codeforces 1032F Vasya and Maximum Matching
题目链接
http://codeforces.com/contest/1032/problem/F
题目大意
给你一棵 n 个节点的树，可以删除任意条边，使得删除完之后的图仅有一种最大匹配的方法。问有多少种删边方法。
题目分析
考虑使用树形 DP 来解决这道题。如果最大匹配的方法是唯一的，说明任意拆出来一条链都是偶数个点的。设 f[x][0/1] 分别为点 x 和儿子中的一个匹配上了，和没匹配上任何一个儿子。则显然有
f[x][1] = \prod{(f[y][0] + f[y][1])}
再来考虑 f[x][0] 的转移方程。很明显，如果 x 和它的一个儿子匹配上的话显然要选取儿子 y 的 f[y][1] 。其余的点 0 和 1 都可以选。注意到， y 的儿子中已经匹配上的儿子和 x 中其他已经匹配上的儿子是可以和它们连边的，因此需要考虑这种情况统计一下即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3e5 + 5;
long long mod = 998244353;
int n, m, t;
vector <int> e[maxn];
long long f[maxn][2];
long long g[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
int addedge(int x, int y){
e[x].push_back(y);
e[y].push_back(x);
return 0;
}
int dfs(int x, int fa){
int y;
int i, j;
f[x][0] = 0;
f[x][1] = 1;
g[x] = 1;
for(auto y : e[x]){
if(y != fa){
dfs(y, x);
f[x][1] = f[x][1] * ((f[y][0] + f[y][1]) % mod) % mod;
g[x] = g[x] * ((2 * f[y][0] + f[y][1]) % mod) % mod;
}
}
for(auto y : e[x]){
if(y != fa){
f[x][0] = (f[x][0] + (g[x] * qpow((2 * f[y][0] + f[y][1]) % mod, mod - 2) % mod) * g[y] % mod) % mod;
}
}
return 0;
}
int main(){
int i, j;
int x, y;
n = read();
for(i=1;i<n;i++){
x = read();
y = read();
addedge(x, y);
}
dfs(1, -1);
printf("%lld\n", (f[1][0] + f[1][1]) % mod);
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3e5 + 5;
long long mod = 998244353;
int n, m, t;
vector <int> e[maxn];
long long f[maxn][2];
long long g[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
int addedge(int x, int y){
e[x].push_back(y);
e[y].push_back(x);
return 0;
}
int dfs(int x, int fa){
int y;
int i, j;
f[x][0] = 0;
f[x][1] = 1;
g[x] = 1;
for(auto y : e[x]){
if(y != fa){
dfs(y, x);
f[x][1] = f[x][1] * ((f[y][0] + f[y][1]) % mod) % mod;
g[x] = g[x] * ((2 * f[y][0] + f[y][1]) % mod) % mod;
}
}
for(auto y : e[x]){
if(y != fa){
f[x][0] = (f[x][0] + (g[x] * qpow((2 * f[y][0] + f[y][1]) % mod, mod - 2) % mod) * g[y] % mod) % mod;
}
}
return 0;
}
int main(){
int i, j;
int x, y;
n = read();
for(i=1;i<n;i++){
x = read();
y = read();
addedge(x, y);
}
dfs(1, -1);
printf("%lld\n", (f[1][0] + f[1][1]) % mod);
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3e5 + 5;
long long mod = 998244353;
int n, m, t;
vector <int> e[maxn];
long long f[maxn][2];
long long g[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
int addedge(int x, int y){
e[x].push_back(y);
e[y].push_back(x);
return 0;
}
int dfs(int x, int fa){
int y;
int i, j;
f[x][0] = 0;
f[x][1] = 1;
g[x] = 1;
for(auto y : e[x]){
if(y != fa){
dfs(y, x);
f[x][1] = f[x][1] * ((f[y][0] + f[y][1]) % mod) % mod;
g[x] = g[x] * ((2 * f[y][0] + f[y][1]) % mod) % mod;
}
}
for(auto y : e[x]){
if(y != fa){
f[x][0] = (f[x][0] + (g[x] * qpow((2 * f[y][0] + f[y][1]) % mod, mod - 2) % mod) * g[y] % mod) % mod;
}
}
return 0;
}
int main(){
int i, j;
int x, y;
n = read();
for(i=1;i<n;i++){
x = read();
y = read();
addedge(x, y);
}
dfs(1, -1);
printf("%lld\n", (f[1][0] + f[1][1]) % mod);
return 0;
}