【每日一题】旅游

题意：给定一棵树，从s点开始，每次选择一个没有染色过的点居住，居住后所有相邻的点都会被染色，问最多住几个点？

solution：树形dp，这题和“没有上司的舞会”几乎完全一样， 表示i点住/不住的最大值，，只不过起点必选，所以答案只可能是 ，

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, s, idx, h[N], dp[N][2];

struct Node {
  int to, next;
} g[N];

void add(int x, int y) { g[idx].to = y, g[idx].next = h[x], h[x] = idx++; }

void dfs(int u, int fa) {
  dp[u][1] = 1;
  for (int i = h[u]; ~i; i = g[i].next) {
    int v = g[i].to;
    if (v == fa) continue;
    dfs(v, u);
    dp[u][0] += max(dp[v][0], dp[v][1]);
    dp[u][1] += dp[v][0];
  }
}

int main() {
  memset(h, -1, sizeof(h));
  cin >> n >> s;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs(s, -1);
  cout << dp[s][1] << '\n';
  return 0;
}