题解 P1623 【[CEOI2007]树的匹配Treasury】
inexistent · · 题解
人生第一道省选/NOI-（其实并没有，可能是因为码量有点大吧）的树形Dp，看着题解还是想了很久（个人认为官方的SOL有点扯）
楼下提到f[i][1]>=f[i][0]，我也没法证明，但这其实本质上和这道题没关系，我们可以通过判断来解决。而且，楼下dalao的dfs里竟然是一个for语句的，而我写了4个……
首先树形Dp是很明显的，f[i][0]表示i的子树中，i不参与匹配的最大匹配数，同样f[i][1]表示i参与匹配的最大匹配数。这样第一个子问题的答案就是Max(f[1][0], f[1][1])。（题目给出的是无根树，我们就把1当根吧）
对于f[i][0]的转移很简单，既然i不参与匹配，那么f[i][0]就是它的每棵子树的最大匹配之和，因为显而易见，两个不同子树内的节点不可能匹配，所以每一个子树是独立的。所以，就是所有儿子v的Max(f[v][0],f[v][1])的总和。（子节点参不参与都没关系）
对于f[i][1]，情况稍稍复杂一点。由于i节点最多只能被匹配一次，所以我们可以这样来考虑。对于节点u，选择其中一个子节点v来和自己匹配，剩余的仍然取最大值，这样剩余的最大值很显然是f[u][0]-Max(f[v][0],f[v][1])，并且除了子节点v，v的其余儿子依然是独立的，所以再加上f[v][0]。所以转移方程即为f[u][1] = Max(f[u][1], f[u][0]-Max(f[v][0],f[v][1])+f[v][0]+1);
然后考虑第二个子问题，方案数怎么办？依然Dp。g[i][k]表示对应的f[i][k]的方案数。但注意了，答案不是g[1][1]，因为有可能f[1][0]==f[1][1]，这时候最大值有两个，所以答案是g[1][0]+g[1][1]。对于其他情况，输出f较大的那个就可以了。
还是先考虑g[i][0]如何转移，对于节点u，它由于是由各个子节点转移过来的，所以总的方案数就是各个子节点最大值方案数的积。还是一样，需要特判一下g[v][0] == g[v][1]的情况。
最难的也就是g[i][1]的转移了。对于这种情况，首先我们需要判断一下哪些节点与根匹配以后会转移出来最大值f[u][1]，而判断这个只需要按照前面的方程再推一遍看看是否相等就可以了。即if(f[u][0]-Max(f[v][0],f[v][1])+f[v][0]+1 == f[u][1])。而这时候，我们还是仿照前面的思维过程，但是注意方案数中除去一部分使用除法而不是减法（前面是由乘法转移过来的），加上也要改成乘上。并且还是要特判f[v][0]==f[v][1]的情况。具体见代码。
想出上面这些并不复杂，而我却在g的初始化上卡了将近一小时。一开始我把每个g[i][0]和g[i][1]都初始化为1，结果挂了。调试千百遍之后把g[i][1]的初始化删掉以后突然就对了。这个现在我是这样理解的，因为我的g[i][0]是要拿去直接乘的，显然不能先赋成0，不然推出来的g[i][0]就全是0了。并且g[i][1]是加的，刚开始如果就是1就会影响结果。这个只不过是一个非常牵强的理解，希望大神能给出证明……
另外这道题要高精也是非常坑的，既然高精模板那么多，我也不好意思盗版权，高精代码就不贴了。
/*written by -=qxz=- */
////////////////////////////////此处省略200行
int n,u,m,v;
vector <int> G[N];
int f[N][2];
BigInteger g[N][2];
inline void AddEdge(int u, int v){
G[u].push_back(v);
}
void DP(int u, int fa){
int v,sz=G[u].size(),not_leaf=0;
for(int i = 0; i < sz; ++i){
if(G[u][i] == fa) continue;
++not_leaf;
}
g[u][0] = 1;
if(!not_leaf){
return;
}
for(int i = 0; i < sz; ++i){
v = G[u][i];
if(v == fa) continue;
DP(v,u);
f[u][0] += Max(f[v][0], f[v][1]);
if(f[v][0] == f[v][1]) g[u][0] *= (g[v][0] + g[v][1]);
else{
if(f[v][0] > f[v][1]) g[u][0] *= g[v][0];
if(f[v][1] > f[v][0]) g[u][0] *= g[v][1];
}
}
f[u][1] = f[u][0];
for(int i = 0; i < sz; ++i){
v = G[u][i];
if(v == fa) continue;
f[u][1] = Max(f[u][1], f[u][0]-Max(f[v][0],f[v][1])+f[v][0]+1);
}
for(int i = 0; i < sz; ++i){
v = G[u][i];
if(v == fa) continue;
if(f[u][0]-Max(f[v][0],f[v][1])+f[v][0]+1 == f[u][1]){
if(f[v][0] == f[v][1] && g[v][0]+g[v][1] != 0){
g[u][1] += g[u][0]/(g[v][0]+g[v][1])*g[v][0];
}
else{
if(f[v][0] > f[v][1] && g[v][0] != 0){
g[u][1] += g[u][0]/(g[v][0])*g[v][0];
}
if(f[v][1] > f[v][0] && g[v][1] != 0){
g[u][1] += g[u][0]/(g[v][1])*g[v][0];
}
}
}
}
}
int main(){
// freopen(".in","r",stdin);
read(n);
for(int i = 1; i <= n; ++i){
read(u);
read(m);
for(int j = 1; j <= m; ++j){
read(v);
AddEdge(u,v);
}
}
DP(1,0);
printf("%d\n",Max(f[1][0], f[1][1]));
if(f[1][0] == f[1][1]) cout << g[1][0]+g[1][1];
else{
if(f[1][0] > f[1][1]) cout << g[1][0];
if(f[1][1] > f[1][0]) cout << g[1][1];
}
return 0;
}