旅游 题解

本题是树形dp，树的最大独立集问题。
自己涂色，那孩子一定不能涂***r>自己不涂色，那孩子无所谓，由于自己也在里面，所以要加一

dp[root][0]+=max(dp[to][0],dp[to][1]);
dp[root][1]+=dp[to][0];

循环外
dp[root][1]+=1;

注意坑点：第一天要在s市住宿，所以答案不是dp数组里的最大值，而是dp[s][1]

#include <bits/stdc++.h>
using namespace std;
vector <int> G[500500];
int dp[500500][2];
void dfs(int root,int pre)
{
    for(int i=0;i<G[root].size();i++)
    {
        int to=G[root][i];
        if(to==pre) continue;
        dfs(to,root);
        dp[root][0]+=max(dp[to][0],dp[to][1]);
        dp[root][1]+=dp[to][0];
    }
    dp[root][1]+=1;
}
int main()
{
    int n,s;
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(s,0);
    printf("%d\n",dp[s][1]);
}