从题目中给出的n个结点n-1条边可知输入的是一棵树，可知是树形DP。
简历二维dp数组，dp[i][0]表示在第i个结点住宿时能旅游的最长天数，dp[i][1]表示不在第i个结点住宿时能旅游的最长天数。第二维只有0和1两个取值，表示是否在第i个结点住下。
在计算dp数组时，采用深度优先遍历。为此，使用邻接表存储树结构。转移函数也比较好推，在i住下时，则dp[i][1]等于不在所有与i邻接的结点住下的最长天数之和。不在i住下时，对每个与i邻接的结点，要对在该结点住下的最长天数以及不在该结点住下的最长天数取最大值。
这里在递归进行深度优先遍历时，要多开一个参数，来记录是从哪一个结点转入这次递归的，以避免死循环的情况。当遍历该结点的邻接表时，遇到转入该结点的结点，则直接跳过，不进行递归。

这里比较有意思的情况是，本来table数组和dp数组是定义在main函数里的，所以深度优先遍历函数dfs开了两个参数来传table数组和dp数组。但是这样做会在第18个用例(共20个)处内存超限。为了使代码能正常AC，只好将table数组以及dp数组定义在main函数外部，作为全局变量，从而节省参数传递的内存开销。

#include <iostream>
#include <vector>

using namespace std;

vector<int> table[500000];
int dp[500000][2];

void dfs(int x, int upper){
    dp[x][0] = 0;
    dp[x][1] = 0;
    for(int i = 0;i < table[x].size();i++){
        int y = table[x][i];
        if(y == upper){
            continue;
        }
        dfs(y, x);
        dp[x][0] += max(dp[y][0], dp[y][1]);
        dp[x][1] += dp[y][0];
    }
    dp[x][1]++;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, initial;
    cin >> n >> initial;
    initial--;
    for(int i = 0;i < n - 1;i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        table[x].push_back(y);
        table[y].push_back(x);
    }
    dfs(initial, -1);
    cout << dp[initial][1];
    return 0;
}