【每日一题】【6月2日】旅游

题意：

给定一棵 $n$ 个节点的树，初始选择节点 $s$ ，之后每次选择可以取一个之前未选择的且不与之前选择的节点相邻的节点，问最多可以取多少个节点？

题解：

树形 $dp$ 。

初始节点 $s$ ，当作树的根。那么之后每次节点选择，都是在已选择节点的子节点树中进行选择。
我们可以尝试把这个过程倒过来，由子节点对应的子树选择的结果来决定当前节点对应的子树的选择。
这样就是经典的树形 $dp$ 了。

如果选择了某一个节点，由题意知它所对应的子节点都不能选。
那么可以设计 $dp$ 状态：

$dp[u][0/1]$ 表示节点 $u$ 是否选择 $(0/1)$ 的情况下，以 $u$ 为根的子树可以选择的最多的节点数。

$0$ 表示选， $1$ 表示不选。

可以列出 $dp$ 方程：

$dp[u][0] = 1 + \sum \limits_v dp[v][1]$
$dp[u][1] = \sum \limits_v max(dp[v][1], dp[v][0])$

$v$ 为 $u$ 的子节点。
在 $u$ 选取的情况下，所有子节点 $v$ 均不能被选择。
在不选 $u$ 的情况下， $v$ 可选可不选。

最后结果即为 $dp[s][0]$ 。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, s, dp[N][2];
vector<int> G[N];
void dfs(int u, int fa = 0) {
    dp[u][0] = 1;
    for(int v : G[u]) {
        if(v == fa) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += max(dp[v][0], dp[v][1]);
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    for(int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(s);
    cout << dp[s][0] << endl;
    return 0;
}