题解 | #旅游#

解题思路：

• 说实话，这题是个烂题，完全是做阅读理解的，表达得还不清不楚，很容易让人理解成走走其中最长的分支。
• 按照wa例测试数据猜测，令$d{p}_{i,0\mathrm{/}1}dp\_\{i,0/1\}$表示在$ii$住宿或不住宿的情况。那么有住宿的情况，则一定不住宿离$ii$距离为1的城市有：$d{p}_{[}i,1]+=d{p}_{i^{\mathrm{\prime }}sson,0}dp\_[i,1]\; +=\; dp\_\{i\text{'}s\backslash \; son,0\}$
• 不住宿的情况：$d{p}_{i,0}+=\max (d{p}_{i^{\mathrm{\prime }}sson,0},d{p}_{i^{\mathrm{\prime }}sson,1})dp\_\{i,0\}\; +=\; \backslash max(dp\_\{i\text{'}s\backslash \; son,0\},dp\_\{i\text{'}s\backslash \; son,1\})$
• 初始化的时候，$d{p}_{i,1}=1\mathrm{，}i\in allnodedp\_\{i,1\}=1，i\; \backslash in\; all\backslash \; node$

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to, next;
}es[1000005];
int head[500005],vst[500005], cnt = 0;
int dp[500005][2];
void add_edge(int from, int to){
    es[++cnt].next = head[from];
    es[cnt].to = to;
    head[from] = cnt;
}
void solve(int i){
    for(int j = head[i]; j; j = es[j].next){
        if (vst[es[j].to]) continue;
        else{
            vst[es[j].to] = 1;
            solve(es[j].to);
            dp[i][1] += dp[es[j].to][0];
            dp[i][0] += max(dp[es[j].to][0],dp[es[j].to][1]);
        }
    }
    return;
}
int main(){
    int n, s, from, to;
    cin>>n>>s;
    dp[s][1] = 1;
    for(int i = 1; i <= n-1; ++i){
        cin>>from>>to;
        add_edge(from, to);
        add_edge(to, from);
        dp[from][1] = 1;
        dp[to][1] = 1;
    }
    vst[s] = 1;
    solve(s);
    cout<<dp[s][1]<<endl;
    return 0;
}