旅游题解树形dp

首先题意说的很清楚，必须从一开始，然后去找最长的旅游天数，那么我们可以看出是在一颗树上面操作的，那么就是树形dp来解决，我们可以定义dp[i][1/0],什么意思呢，就是第i个地方我是选择住宿还是不住宿（1/0）的最长停留时间，那么我们如果到了以X为根的节点，如果要住那就是dp[x][1]=dp[y][0]+1,父节点住宿了那么儿子节点必然不可以住宿，然后如果没有住宿是不是就是dp[x][0]+=max(dp[y][1],dp[y][0])

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
vector<int>ans[1<<20];
int dp[1<<20][2];
void dfs(int x,int fa)
{
    dp[x][1]=1,dp[x][0]=0;
    for(auto v:ans[x])
    {
        if(v==fa) continue;
        dfs(v,x);
        dp[x][1]+=dp[v][0];
        dp[x][0]+=max(dp[v][1],dp[v][0]);
        // cout<<x<<" "<<dp[x][0]<<" "<<dp[x][1]<<endl;
    }
}
int main()
{
    fio;
    int n,s;
    cin>>n>>s;
    for(int i=1,u,v; i<=n-1; i++)
    {
        cin>>u>>v;
        //u=read(),v=read();
        ans[u].push_back(v);
        ans[v].push_back(u);
    }
    dfs(s,-1);
    cout<<dp[s][1];
    return 0;
}