洛谷题目： P2996 [USACO10NOV] Visiting Cows G 题解

题目传送门：

P2996 [USACO10NOV] Visiting Cows G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前言：

本题的核心问题是在一棵由奶牛（节点）和道路（边）构成的树状结构中，根据 “不能同时拜访直接相连的两个奶牛” 这一限制条件，找出贝茜能够拜访的奶牛的最大数量，难度为中下一点。

#本题具体思路和步骤：

        1、问题抽象与数据结构选择：

                1.1、输的抽象：

                        题目中提到了 N 个奶牛， 我们通过  N - 1  条道路相连，并且任意两头奶牛之间的连接关系可以抽象成一棵树，每头奶牛是数的一个节点，道路是树的边。

                1.2、邻接表存储：

                        为了表示这棵树，我们使用邻接表来存储节点之间的连接关系。邻接表是一种常用的图（树是一种特殊的图）的存储方式，对于每个节点 u，使用一个数组 adj[u] 来存储与它直接相连的所有节点。

        2、动态Dp思想引入：

                1.1、状态定义：

                        设  dp[u][o] 表示不选组该节点 u 时，以 u  为根的子树中可拜访最大奶牛数量。

                        设  dp[u][1]  表示x厕节点  u 时，以 u 为根的子树中可拜访的最大奶牛数量。

                1.2、状态转移的核心思路：

                        我们通过递归地考虑每个节点及其子节点的选择情况，利用子问题的解来构建当前节点的解。

        3、状态转移方程推导：

                1.1、不选择节点 u 的情况：

                        当不选择节点 u 时，对于 u 的每个节点 v ，我们可以自由选择是否拜访 v 。因为不选 u 不会对 v 的选择产生直接限制，所以我们要在 v 选择 dp[v][1] 和不被选择 dp[v][0] 这两种情况中取最大值，然后将所有子节点的这些最大值累加起来，就得到了 dp[u][0] 这两种情况中取最大值，然后将所有子节点的这些最大值累加起来，就得到了 dp[u][0]。即 dp[u][0]=sum(max(dp[v][0],dp[v][1]))，这里的 sum 表示为 u 的所有子节点 v 进行累加。

                1.2、选择节点 u 的情况：

                        当选择节点 u 时，根据题目要求，与 u 直接相连的子节点都不能被选择。所以 u 的子节点 v 只能处于不被选择的状态。我们先将节点 u 本身计入，然后把所有子节点不被选择状态下的数量累加起来，就得到了 dp[u][1]。即 dp[u][1]=1+sum(dp[v][0])。

        4、深度优先搜索实现：

                1.1、递归遍历树：

                        使用深度优先搜索算法来遍历整棵树。从树的任意一个节点开始，递归地访问每个节点及其子节点。

                1.2、计算 dp 值：

                        在递归访问的过程中，对于每个节点 u ，先初始化 dp[u][0]=0 和 dp[u][1]=1。然后遍历 u 的所有子节点 v ，根据上述状态转移方程更新 dp[u][0] 和 dp[u][1] 的值

        5、结果计算：

                整棵树遍历完成后，最终的结果就是根节点在选择何不选择当中，两种状态下可拜访奶牛数量的最大值，即 max(dp[1][0],dp[1][1])。

##复杂度分析：

        1、时间复杂度：

                由于深度搜索会遍历树中的每个节点和每条边一次，树有 n 个节点和 n - 1 条边，所以时间复杂度为 O(n)。

        2、空间复杂度：

                主要的空间开销在于邻接表和 dp 数组。邻接表存储树的结果需要 O(n) 的空间， dp 数组存储每个节点的两种状态也需要 O(n) 的空间，因此空间复杂度为 O(n)。

###代码：

#include <bits/stdc++.h>
using namespace std;const int MAXN = 50005;
vector<int> adj[MAXN];  // 邻接表存储树的结构
int dp[MAXN][2];  // dp数组，dp[u][0] 表示不选节点u，dp[u][1] 表示选节点u// 深度优先搜索函数，用于计算dp数组
void dfs(int u, int p) {dp[u][0] = 0;dp[u][1] = 1;for (int v : adj[u]) {if (v != p) {dfs(v, u);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 = 0; i < n - 1; i++) {int c1, c2;cin >> c1 >> c2;adj[c1].push_back(c2);adj[c2].push_back(c1);}// 从节点1开始进行深度优先搜索dfs(1, 0);// 输出最大可拜访的奶牛数量cout << max(dp[1][0], dp[1][1]) << endl;return 0;
}