每日一天 6.2 旅游

这是一道树形dp题（一开始我当贪心写 只能过样例.....）
对于一个节点我们有选与不选两种状态
我们定义 dp[i][0] dp[i][1] 为 不选i节点 和 选i节点 能停留的最长时间
选一个节点 那么它就 初始化为1 dp[i][1]=1;
它的子节点一定不能选 dp[i][1]+=dp[j][0];
如果不选 那么子节点可选可不选 dp[i][0]+=max(dp[j][0],dp[j][1]);
这就是递推方程

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int const N=5e5+5;
int n,s,tot,head[N],nex[N<<1],to[N<<1],vis[N],dp[N][2];///链式前向星
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
void  dfs(int u,int fa)
{
     dp[u][1]=1;///选择u这个点住下 初始化为1
     for(int j=head[u];j;j=nex[j])///遍历i起点的每一条边
     {
                int v=to[j];///连接的点
                if(v==fa) continue;
                dfs(v,u);
                dp[u][0]+=max(dp[v][0],dp[v][1]);///不选u点住下  子节点可选可不选  求最大
                dp[u][1]+=dp[v][0];/// 住下  子节点一定不能住
     }
}
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n-1;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
    }
    dfs(s,0);
    int  ans=dp[s][1];
    cout<<ans<<endl;
}