企业官网建设流程全解析

本来想继续学难度高一点的区间dp问题，发现好像能力不够，还是把这些基础的dp问题掌握在进阶吧，这篇就以树形dp为主，将树形dp的基础问题解决搞懂，完成阶段一的主要任务。

这类问题算是结合了深搜和dp，不断的递归求出最小值和最大值，需要熟练的掌握递归的方法。

1.P1352 没有上司的舞会

（1）核心思路

这种题我已经看过很多类似的，但是以前永远都写不出。树形dp的核心就在于选与不选，而这题有根节点作保障，我们可以从根节点开始判断，选or不选，设一个dp[N][2]，也就是说dp[N][0]的时候为不选，dp[N][1]的时候为选，一维代表的是其编号。

（2）寻找根节点，为搜索做准备

想要递归，我们必须找到源头，也就是根节点，依据题目的要求总会有一个是老大，我们先假设所有的编号都是根：

for(int i=1;i<=n;i++) { cin >> r[i]; is_root[i]=true; }

然后根据第 (n+2) 到第 2n 行的输入，导入父亲节点和子节点，再将这些子节点从is_root里面排查出去：

for(int i=0;i<n-1;i++) { int l,k; cin >> l >> k; son[k].push_back(l); is_root[l]=false; }

最后再设一个root，从1到n循环一遍，找出那个唯一为true的根节点：

int root; for(int i=1;i<=n;i++) { if(is_root[i]) root=i; }

这样我们既找出了根节点，也将所有父与子关系的节点整理出来了，为我们后续执行递归dp做了充足的准备。

（3）编写核心代码，寻找最大快乐值

思路理清，也做好了前提准备，现在绝对可以看懂代码，以及对于掌握递归的同学能几乎想出接下来的步骤，定义一个dfs函数，将root值导入进去，0的时候是不选，1的时候是选，再去它的子节点里面找，又从子节点里面找子节点，依次循环下去，最后又把值传入根节点，代码如下：

void dfs(int u) { dp[u][0]=0; dp[u][1]=r[u]; for(int v:son[u]) { dfs(v); dp[u][0]+=max(dp[v][0],dp[v][1]); dp[u][1]+=dp[v][0]; } }

这题就是要将dfs插入正确的位置，而不是插入在循环外，也不是在循环的末尾。

本题完整代码如下：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=6e3+10; int r[N]; int dp[N][2]; vector <int> son[N]; bool is_root[N]; void dfs(int u) { dp[u][0]=0; dp[u][1]=r[u]; for(int v:son[u]) { dfs(v); dp[u][0]+=max(dp[v][0],dp[v][1]); dp[u][1]+=dp[v][0]; } } int main() { int n; cin >> n; for(int i=1;i<=n;i++) { cin >> r[i]; is_root[i]=true; } for(int i=0;i<n-1;i++) { int l,k; cin >> l >> k; son[k].push_back(l); is_root[l]=false; } int root; for(int i=1;i<=n;i++) { if(is_root[i]) root=i; } dfs(root); cout << max(dp[root][1],dp[root][0]); return 0; }

2.P2016 [SEERC 2000] 战略游戏

（1）设计思路

这题是个无根树，且没有方向，可以看成一个图，每个点都可以为出发点，既是父节点，也是子节点。这道题的核心解题方法同样也是选与不选，当选了一个点（士兵）那么周围的点按道理就不需要选了，除特殊情况外。懂得这个道理我们可以快速入手了。

（2）做好前提准备

将每个连接的节点都互相导入成对方的父节点和子节点，代码如下：

int n; cin >> n; for(int i = 0; i < n; i++) { int x, k; cin >> x >> k; while(k--) { int r; cin >> r; son[x].push_back(r); son[r].push_back(x); } }

（3）全面考虑，完成核心代码

void dfs(int u, int fa) { dp[u][1] = 1; // 当前点放士兵 dp[u][0] = 0; // 当前点不放 for(int v : son[u]) { if(v == fa) continue; dfs(v, u); dp[u][1] += min(dp[v][1],dp[v][0]); dp[u][0] += dp[v][1]; } }

核心的dfs代码和上一题的代码大同小异，但是我们会发现dfs有两个变量，一个u和一个多出的fa，u大家都理解，就是导入的根节点，这里我们第一个导入的是1，那么fa又是什么呢？fa是father的简写，这里的作用就是当遍历到1的子节点2时，经过递归，2的子节点含有1、3、4，那么又会重复遍历1和2这个选项，导致死循环，所以用一个fa帮助我们解决这个问题。

而现在我们会发现，为什么我们在dp[u][1] += min(dp[v][1],dp[v][0]);要使用min，因为dp[v][0]不肯定要比dp[v][1]小吗，其实不然，例如我们以根节点为1为例，初始选1的话那么我们选择的安放点就为1、3、4。如果不选1，那么选择点为2、4、6。而我们会发现最好的放置点应该为2、4两个放置点，这也解释了为什么我们需要使用min来找出最小值。

本题完整代码如下：

#include <bits/stdc++.h> using namespace std; const int N = 1510; vector<int> son[N]; int dp[N][2]; // 带父亲防回走 void dfs(int u, int fa) { dp[u][1] = 1; // 当前点放士兵 dp[u][0] = 0; // 当前点不放 for(int v : son[u]) { if(v == fa) continue; dfs(v, u); dp[u][1] += min(dp[v][1],dp[v][0]); dp[u][0] += dp[v][1]; } } int main() { int n; cin >> n; for(int i = 0; i < n; i++) { int x, k; cin >> x >> k; while(k--) { int r; cin >> r; son[x].push_back(r); son[r].push_back(x); } } dfs(0, -1); cout << min(dp[0][0], dp[0][1]); return 0; }

3.P12317 [蓝桥杯 2024 国 C] 树的结点值

（1）拆解题意，理清思路

很直观的树形dp题，依然是通过深搜+dp的方法，有上面两个题目给我们打基础，写这题多多少少会有一点思路。想要知道某节点的值，我们需要知道在它之下所有节点的奇偶性，但我们不能通过暴力搜索的方式将这个节点之下的所有奇偶的值都获取，我们通过递归，可以从最下层一层一层的传上来。

（2）实现代码功能

我们可以定义两个数组，一个记录奇数的个数，一个记录偶数的个数。我们通过深搜的方式将底层的奇偶值一层一层的向上传上来，如果该节点是偶数，那么我们就在偶数节点的个数上加上一，奇数节点的值不变，反之同理。

#include <bits/stdc++.h> using namespace std; const int N=2e5+10; vector <int> f[N]; int cnt_0[N],cnt_1[N]; void dfs(int u) { if(u%2==0) { cnt_0[u]=1; cnt_1[u]=0; } else { cnt_0[u]=0; cnt_1[u]=1; } for(int v:f[u]) { dfs(v); cnt_0[u]+=cnt_0[v]; cnt_1[u]+=cnt_1[v]; } } int main() { int n; cin >> n; for(int i=2;i<=n;i++) { int fi; cin >> fi; f[fi].push_back(i); } dfs(1); for(int i=1;i<=n;i++) { if(i%2==0) cout << cnt_0[i]; else cout << cnt_1[i]; cout << endl; } return 0; }

可以说这题甚至都没有用到dp，但是思路和上面两道dp的题大同小异，将dp拆分为两个代表奇偶数个数的数组。

4.P14919 [GESP202512 六级] 路径覆盖

（1）理清思路，构思题解

这题是我认为很有意思的一道题，最开始我还没有理解这道题的意思，以为是每个子节点，结果发现是叶子节点向上传输需要经过一个染黑的节点。但是我们要怎么找到那个叶子节点并且能直接往上回溯，这是我当时想不到的点。这题的核心解题思路就是，快速判断是否为叶子节点，将数据往上传输。

（2）完成代码

这题的代码的强大之处就是既找出了叶子节点，也找到了最小的值，真的能理解其微妙之处的才能感受到代码的力量，如此精简没有任何累赘。代码如下：

#include <bits/stdc++.h> using namespace std; const int N=1e5+10; vector <int> son[N]; int dp[N]; long long c[N]; void dfs(int u) { long long sum=0; bool is_leaf=true; for(int v:son[u]) { is_leaf=false; dfs(v); sum += dp[v]; } if(is_leaf) { dp[u]=c[u]; } else { dp[u]=min(sum,c[u]); } } int main() { int n; cin >> n; for(int i=2;i<=n;i++) { int f; cin >> f; son[f].push_back(i); } for(int i=1;i<=n;i++) { cin >> c[i]; } dfs(1); cout << dp[1]; return 0; }

这个sum的作用不仅仅是简单的统计，而我认为此代码的精妙之处，就是当4、5的染黑值传上来之后，我们需要判单它们的父节点2是否能代替两个节点的染黑值，因为2在4、5两个叶子节点的路径上，所以此时的sum不是全局的sum而是当下2节点之下的子节点的sum值，将这个sum与2的值作比较，就解决了这个代码最核心的几个问题。

这次的分享就到此为止，这算是几个比较基础的树形dp题目，也许3、4题的解析比较简略，但是我已经在最初的几道题解析了这类题目的核心思想，我相信只要理解了这类思想，都可以理解我之后的分析。

最后想说下我个人在最近写题的一些心得，在我身边很多人的学习新知识的方法都是通过大量的写题以及抄写理解，但我的方法不一样，在刚刚起步的时候我认为我需要花费更多的时间去拆解这些知识点的内涵，我初期写题花费的时间也许是别人的几倍，我写一道题可能就花费了1到2个小时，去疯狂拆解题意，去找网课学习，但是我觉得题目在精不在多，若不去理解题目深层的含义，我认为至少对于我来说我的路是走不远的，永远无法向更高难度的题目进阶。