题目大意
小C学习了二分图匹配，二分图是一种特殊的图，其中的点可以分到两个集合中，使得相同的集合中的点两两没有连边。
图的“匹配”是指这个图的一个边集，里面的边两两不存在公共端点。
匹配的大小是指该匹配有多少条边。
二分图匹配我们可以通过匈牙利算法得以在O(VE)时间复杂度内解决。
小C觉得单纯的二分图匹配算法毫无难度，因此提出新的问题：
现在给你一个$N$个点$N-1$条边的连通图，希望你能够求出这个图的最大匹配以及最大匹配的数量。
两个匹配不同当且仅当存在一条边在第一个匹配中存在而在第二个匹配中不存在。
题目分析
石室中学企鹅强弱化版。
设$f[i,0/1]$为第$i$个点不匹配/与儿子匹配 的最大匹配。
$g[i,0/1]$表示方案数。
对于方案数怎么处理呢？
对于$g[i,0]$当然是哪边大从哪边转移过来啊，累乘一下（见代码）。
那$g[i,1]$怎么办？
观察$f[i,0]$与$f[i,1]$的转移式一模一样，因此可以先对所有儿子将$f[i,0],g[i,0]$转移出来，再考虑更新$g[i,1]$。
其中$Rec[j]$表示的是$j$的决策点的$g[]$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
const LL mod=1e9+7;
int t,p,n;
LL f[maxn][2],g[maxn][2],Rec[maxn];
vector<int>edges[maxn];
void Clear() {
memset(Rec,0,sizeof(Rec));
for(int i=1; i<=n; i++)edges[i].clear();
}
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
LL Quick_Pow(LL a,LL b) {
LL ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
LL inv(LL a) {
return Quick_Pow(a,mod-2);
}
void TreeDp(int Now,int fa) {
f[Now][0]=f[Now][1]=0;
g[Now][0]=g[Now][1]=1;
if(edges[Now].size()==1)g[Now][1]=0;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==fa)continue;
TreeDp(Next,Now);
f[Now][0]+=max(f[Next][0],f[Next][1]);
if(f[Next][0]>f[Next][1]) {
g[Now][0]=g[Now][0]*g[Next][0]%mod;
Rec[Next]=g[Next][0];
} else if(f[Next][0]<f[Next][1]) {
g[Now][0]=g[Now][0]*g[Next][1]%mod;
Rec[Next]=g[Next][1];
} else {
g[Now][0]=g[Now][0]*(g[Next][0]+g[Next][1])%mod;
Rec[Next]=(g[Next][0]+g[Next][1])%mod;
}
}
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==fa)continue;
LL _f=f[Now][0]-max(f[Next][0],f[Next][1])+f[Next][0]+1,_g=g[Now][0]*inv(Rec[Next])%mod*g[Next][0]%mod;
if(f[Now][1]<_f) {
f[Now][1]=_f;
g[Now][1]=_g;
} else if(f[Now][1]==_f)g[Now][1]=(g[Now][1]+_g)%mod;
}
}
int main() {
t=Get_Int();
p=Get_Int();
while(t--) {
n=Get_Int();
Clear();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
TreeDp(1,0);
printf("%lld ",max(f[1][0],f[1][1]));
if(p==2) {
LL ans=0;
if(f[1][0]>=f[1][1])ans=(ans+g[1][0])%mod;
if(f[1][0]<=f[1][1])ans=(ans+g[1][1])%mod;
printf("%lld\n",ans);
} else putchar('\n');
}
return 0;
}
|
