题目的主要信息：

• 地图上有 n 个城市，它们之间通过 n-1 条道路联通，即一棵无向树
• 第一天会在 s 市住宿，并游览与它距离不超过 1 的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过 1 的所有城市
• 不能住在一个已经浏览过的城市，最多要游览多少天

因为每个会去到与这个城市相连的所有不重复城市，因此每天住宿的城市都是不相邻的，即求树上最多的不相邻的点的问题（最大独立集）

具体做法：

可以用树型dp，对于某一个结点，是否选择这个点进入集合，我们用dp数组表示，$dp[i][0]dp[i][0]$表示以$ii$结点为根的子树，不选取该结点时的最大独立集的数量，$dp[i][1]dp[i][1]$则表示以$ii$结点为根的子树，选取该结点时的最大独立集的数量，那么dfs构建这个dp数组以后，$dp[s][1]dp[s][1]$就是我们需要的答案了。

我们dfs遍历树，构建这个dp数组，每次先进入子树，算子树的dp，然后轮到自己，如果选取了这个结点本身，那么与该节点相邻的结点都不能选，$dp[cur][1]+=dp[next][0]dp[cur][1]\; +=\; dp[next][0]$，如果没有选取该结点本身，对于子节点可以选也可以不选，我们取最大值即可，$dp[cur][0]+=max(dp[next][1],dp[next][0])dp[cur][0]\; +=\; max(dp[next][1],dp[next][0])$。因为一个结点可能有多个子节点，子节点的子树之间不会相邻，因此是累加。

图中住过的地方也是游览过的：

#include<iostream>
#include<vector>
using namespace std;

int dp[500001][2];
vector<int> G[500001];

void dfs(int cur, int pre){
    for(int i = 0; i < G[cur].size(); i++){ //遍历所有子节点
        int next = G[cur][i];
        if(next == pre) //不能重复遍历
            continue;
        dfs(next, cur); //进入子树
        dp[cur][0] += max(dp[next][1],dp[next][0]); //不选该结点时，取子节点最大值
        dp[cur][1] += dp[next][0]; //该结点选了自己，不能选相邻的子结点
    }
}

int main(){
    int n, s;
    cin >> n >> s;
    for(int i = 1; i <= n; i++) //初始化每个结点都选取自己的情况
        dp[i][1] = 1;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); //构建树
        G[v].push_back(u);
    }
    dfs(s, -1); //dfs遍历树
    cout << dp[s][1] << endl; 
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，dfs遍历树的所有结点
• 空间复杂度：$O(n)O(n)$，无论是构建邻接表的数组还是dp数组都是$O(n)O(n)$