自动搬运

查看原文

来自洛谷，原作者为

	2024sdhkdj **

搬运于2025-08-24 22:45:55，当前版本为作者最后更新于2023-10-02 12:46:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面传送门

我的 BLOG

前置知识： 树形 DP

题意描述

给定两个数 $m$、$n$，表示有 $m$ 棵 $n$ 个点的树。其中每棵树形态、结构相同，给定它们的 $n-1$ 条边。需要你为每棵树上的所有结点赋值，令 $a(i,j)$ 表示为第 $i$ 棵树上的第 $j$ 个点被赋的值。赋值规则如下：

• 对于每棵树上任何一个结点，只能赋值为 $0$ 或 $1$。

• 对于每棵树上相同位置的节点，允许有其中一个结点赋值为 $1$。

• 对于每棵树上任意一条边，允许有其中一个端点赋值为 $1$。

要求出有多少种赋值方案数。

算法分析

因为要求方案数，可以想到使用 DP。而题目要求是在树上操作，可以确定是树形 DP。

定义状态

树形 DP 的状态比较套路，一般设两维（$dp[i][j]$）。第一维表示“以 $i$ 为根结点的字树”，第二维根据题意要求，表示 $i$ 号位置为 $j$。意义什么呢？因为题目所求是赋值方案，于是可以断定：

$dp[i][j]$ 表示，以 $i$ 为根结点的子树，第 $i$ 号位置为 $j$ 的方案数。

但这个状态有一个小错误，假如其中一棵树 $i$ 号位置为 $1$，则其他树必须为 $0$，而不能全部为 $1$。因此需要分类讨论：

1. 当 $j=0$ 时：

   $dp[i][j]$ 表示，以 $i$ 为根结点的子树，第 $i$ 号位置为 $0$ 的方案数。

2. 当 $j=1$ 时：

   $dp[i][j]$ 表示，以 $i$ 为根结点的子树，其中一棵树第 $i$ 号位置为 $1$，其他树为 $0$ 的方案数。

状态转移方程

个人认为，找状态转移方程是此题的难点。一旦推出来了，剩下的就只是打板子了。

根据我们定义的状态，需要分两种情况讨论：

1. 当第 $i$ 位为 $0$ 时：

   • 当它的儿子为 $0$ 时：

     为以前的方案数乘以这个儿子的方案数：$dp[i][0] = dp[i][0] \times dp[son][0]$。

   • 当它的儿子为 $1$ 时：

     对于每棵树的它的这个儿子的位置，都可以为 $1$，根据乘法原理，为以前的方案数乘以 $m$ 种为 $1$ 的方案数：$dp[i][0] = dp[i][0] \times m \times dp[son][1]$。

2. 当第 $i$ 位为 $1$ 时：

   • 当它的儿子为 $0$ 时：

     同样为以前的方案数乘以这个儿子的方案数：$dp[i][1] =dp[i][1] \times dp[son][0]$。

   • 当它的儿子为 $1$ 时：

     对于每棵树的它的这个儿子的位置，除了它本身的儿子，其他的都可以为 $1$，根据乘法原理，为以前的方案数乘以 $m-1$ 种为 $1$ 的方案数：$dp[i][1] =dp[i][1]\times (m-1) \times dp[son][1]$。

合并得：

1. $dp[i][0] =dp[i][0]\times (dp[son][0]+m \times dp[son][1])$。

2. $dp[i][1] =dp[i][1] \times (dp[son][0]+(m-1) \times dp[son][1])$。

答案

根据我们定义的状态，答案为：以根结点为根的树，所有树根结点为 $0$ 或任意一棵树根结点 $1$ 的方案数之和。即：

初始状态

根据状态转移方程，因为需要乘，如果每个 $dp[i][j]$ 设为 $0$，则最终答案只能为 $0$。因此将所有 $dp[i][j]$ 设为 $1$，即： $\forall i \in [1,n],\forall j \in [0,1]$，有 $a_{(i,j)}\in\{1\}$。

注意事项

• 因为是树，要建双向边，且在 dfs 时需要判父亲，不然会不断走重复的路，直至卡死。

• 方案数可能很大，记得每转移一次就取模一次，并开 long long。

• 一定记得先搜索再转移，不然它的儿子的方案数还未算出，转移是无效的。

• 有表达不当出可以辅以代码注释理解。

代码

#include<bits/stdc++.h>
#define mod 1000000007//模数
using namespace std;
const int N=1e6+10;
int n,m;
long long dp[N][2];//记得开long long
vector<int> vec[N];
void dfs(int cur,int fa){//因为是无向边，需要记录它的父亲以避免重复
	for(int i=0;i<vec[cur].size();i++){
		int to=vec[cur][i];
		if(to==fa)//判断父亲
			continue;
		dfs(to,cur);//先搜索，再转移，不然dp[to][0/1]还没有算出来，转移无效
		dp[cur][0]=(dp[cur][0]*(dp[to][0]+m*dp[to][1]%mod))%mod;
		dp[cur][1]=(dp[cur][1]*(dp[to][0]+(m-1)*dp[to][1]%mod))%mod;//状态转移
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		vec[u].push_back(v);
		vec[v].push_back(u);//记得存双向边
	}
    for(int i=1;i<=n;i++)
        dp[i][0]=dp[i][1]=1;//初始状态
	dfs(1,0);//从根结点深搜
	cout<<(dp[1][0]+m*dp[1][1]%mod)%mod;//答案
	return 0;
}

AC 记录

总结

此题的难点主要是找出状态转移方程，一旦找到了，其他问题也迎刃而解。如何找到呢？最重要的是理解题意和所求。在理清他们的关系后，经过模拟与假设，逐渐摸索出正解。当然，树形 DP 这一类题的细节也挺多的，我深有体会，有可能就是一个符号的差距，就是一片红和一片绿的差距。 因此，多注重细节，才能在考场上稳中求胜。

插句题外话，CSP2023 即将到来，这有可能是我考前最后一次写题解了。在此预祝各位： CSP2023 $RP+\infty$!!!