旅游（树形dp，树上最大独立集）

题目：

给一个树形城市网络。一开始住在s城，第一天游览距离s城≤1的城市，然后住进另一个未游览的城市，第二天重复游览步骤。问最多能游览多少天。

做法：

题意转化一下，让你选尽量多的城市，使城市之间两两不相邻。这就是树上的最大独立集问题。
树形dp，dp[u][0/1]表示点u选/不选时，子树u下的最大独立集的点的数量。 $dp[u][0] = 1+\sum{dp[v][1]};$ u选了，儿子v就不能选。 $dp[u][1] = \sum{max(dp[v][0], dp[v][1])};$ u不选时，儿子v可选可不选。
城市网络以s为根，答案是dp[s][1]

代码：

#include <bits/stdc++.h>
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 5e5 + 7;
int n, s, dp[N][2];
vector<int> g[N];
void dfs(int u, int p){
    dp[u][0] = 1;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += max(dp[v][0], dp[v][1]);
    }
}
int main(void){    
    IOS;
    cin >> n >> s;
    for (int i = 0; i < n-1; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(s, s);
    cout << dp[s][0] << endl;
    return 0;
}