P9161 Trees 题解
2024sdhkdj
·
·
题解
题面传送门
我的 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。意义什么呢？因为题目所求是赋值方案，于是可以断定：
但这个状态有一个小**错误**，假如其中一棵树 $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$ 的方案数之和。即：
$$ans=dp[1][0]+m \times dp[1][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 记录](https://www.luogu.com.cn/record/127023868)**
## 总结
此题的难点主要是找出**状态转移方程**，一旦找到了，其他问题也迎刃而解。如何找到呢？最重要的是理解题意和所求。在理清他们的关系后，经过模拟与假设，逐渐摸索出正解。当然，树形 DP 这一类题的细节也挺多的，~~我深有体会，有可能就是一个符号的差距，就是一片红和一片绿的差距。~~ 因此，多注重细节，才能在考场上稳中求胜。
插句题外话，CSP2023 即将到来，这有可能是我考前最后一次写题解了。在此预祝各位： **CSP2023** $RP+\infty$!!!