自动搬运

查看原文

来自洛谷，原作者为

	inexistent **

搬运于2025-08-24 21:27:13，当前版本为作者最后更新于2018-05-18 20:40:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

人生第一道省选/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;
}