【每日一题】旅游 题解

Description

Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。
旅行地图上有n个城市，它们之间通过n-1条道路联通。
Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。
他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。
XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

Solution

树上最大独立集问题。树的最大独立集，就是这样的一个集合，这些集合里面的点在树中互不相邻。
树形dp可以解决这个问题, 表示不在 的最大独立集, 表示在最大独立集里
显然有递推方程

不要忘记 ， 自己也在最大独立集里。
最后答案就是

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 1024523;
const int N = 5e5 + 5;

vector<int> G[N];
void addedge(int u, int v) {
  G[u].push_back(v);
}
int dp[N][2];
void dfs(int u, int par) {
  dp[u][0] = dp[u][1] = 0;
  for(int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if(v == par) continue;
    dfs(v, u);
    dp[u][1] += dp[v][0];
    dp[u][0] += max(dp[v][1], dp[v][0]);
  }
  dp[u][1]++;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n, s;
  cin >> n >> s;
  for(int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    addedge(u, v);
    addedge(v, u);
  }
  dfs(s, -1);
  cout << dp[s][1] << "\n";
  return 0; 
}