题目

题目描述：
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数组的含义。

  1. 那么首先我们来确定dp数组是干啥用的：我们题目讲到了住宿的节点和节点的住宿问题。
  2. 所有我们的dp数组就定为一个二维数组：dp[i][0/1]=x：第i个节点（住/不住）时的节点数最大值（答案的最大值）。
  3. 接下来就是递推了。
  4. 递推和我们节点之间的关系密不可分：我们这里的节点关系就是我们上面讲到的：住宿点的邻接点不能住宿。

4）算法操作

  1. 怎么操作呢？首先我们是用递归的方法遍历所有节点进行计算。我们自然就从叶子往上计算。
  2. 因为如果住下来，就表示答案会加一，所以我们给每一个住宿的情况都先初始化为1： 
    dp[u][1] = 1;
  3. 然后我们就开始循环遍历子节点，并递归到叶子为止。
  4. 接下来我们就可以递推了，按照我们上面所说的规律可以得到转移方程： 
    dp[u][0] += max(dp[v][0], dp[v][1]);
//我如果不住，下一个随便你住不住，所以选最大的
dp[u][1] += dp[v][0];
//我如果住，下一个必须是不住
  5. 如此递推就可以了。

5）打代码

  1. 我们还是老方法，先用前向星保存树。
  2. 然后按照上面的算法操作进行一遍dfs。
  3. 最后输出一个dp[s][1]就好了，为啥是dp[s][1]？因为我们最后会把答案合并到起点，而起点一定住宿，所以输出这个。
  4. 看我代码咯~

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];
        //我如果住，下一个必须是不住
    }
}
//函数区