【每日一题】旅游
旅游
https://ac.nowcoder.com/acm/problem/15748
题目
题目描述：Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。
旅行地图上有n个城市，它们之间通过n-1条道路联通。
Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。
他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。
XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！
输入描述：
第一行，两个正整数n和s，表示城市个数和第一天住宿的城市s。
接下来n-1行，每行两个整数x和y，表示城市x与城市y之间有一条双向道路。
输出描述：
第一行，一个非负整数表示答案。
解析
1）知识点
- 这道题明显就是一道树的题目，关于树我们能想到的就是dfs，bfs，树形dp。这道题就是一道树形dp。
2）看题目
- 首先我们看题目意思就是：我们每一个住宿节点相邻的位置是不能住宿的，而不能住宿的节点相邻位置住不住宿都可以。
- 最后我们要求出一共有多少个住宿的节点。
3）算法分析
- 既然我们已经知道这是一道树形dp的题目了，那当然就少不掉这句话：动态规划最重要的就是递推和dp数组的含义。
- 那么首先我们来确定dp数组是干啥用的：我们题目讲到了住宿的节点和节点的住宿问题。
- 所有我们的dp数组就定为一个二维数组：dp[i][0/1]=x：第i个节点（住/不住）时的节点数最大值（答案的最大值）。
- 接下来就是递推了。
- 递推和我们节点之间的关系密不可分：我们这里的节点关系就是我们上面讲到的：住宿点的邻接点不能住宿。
4）算法操作
- 怎么操作呢？首先我们是用递归的方法遍历所有节点进行计算。我们自然就从叶子往上计算。
- 因为如果住下来，就表示答案会加一，所以我们给每一个住宿的情况都先初始化为1：
dp[u][1] = 1;
- 然后我们就开始循环遍历子节点，并递归到叶子为止。
- 接下来我们就可以递推了，按照我们上面所说的规律可以得到转移方程：
dp[u][0] += max(dp[v][0], dp[v][1]); //我如果不住，下一个随便你住不住，所以选最大的 dp[u][1] += dp[v][0]; //我如果住，下一个必须是不住
- 如此递推就可以了。
5）打代码
- 我们还是老方法，先用前向星保存树。
- 然后按照上面的算法操作进行一遍dfs。
- 最后输出一个dp[s][1]就好了，为啥是dp[s][1]？因为我们最后会把答案合并到起点，而起点一定住宿，所以输出这个。
- 看我代码咯~
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 5e5 + 7;
int head[MAX], tot;
struct EDGE {
int u, v, w, next;
} edge[MAX << 1];
int n, s;//节点数，起点
int dp[MAX][2];//表示某个节点在（有/没有）的情况下最大待的时间
//全局变量区
void init();//前向星初始化
void add_edge(int u, int v);//前向星加边
void dfs(int u, int fa);//前向星dfs
//函数预定义区
int main() {
IOS;
cin >> n >> s;
init();
for (int i = 1; i <= n - 1; i++) {
int u, v; cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
dfs(s, 0);
cout << dp[s][1] << endl;
return 0;
}
void init() {
memset(head, 0, sizeof head); tot = 0;
}
void add_edge(int u, int v) {
tot++;
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
dp[u][1] = 1;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (v == fa) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
//我如果不住，下一个随便你住不住，所以选最大的
dp[u][1] += dp[v][0];
//我如果住，下一个必须是不住
}
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
字节跳动公司氛围 552人发布