旅游

难度：3星

这道题要求我们在树上取尽可能多的点，但要求不能有两个点相邻。并且要求 $ss$ 点一定要取到。

和“不相邻取数”那道题思路类似，我们定义 $dp[i][0]dp[i][0]$ 代表不取 $ii$ 点时，以 $ii$ 为根的子树能取的点数量最大值。定义 $dp[i][0]dp[i][0]$ 代表取了 $ii$ 点时，以 $ii$ 为根的子树能取的点数量最大值。

然后我们以 $ss$ 为根进行dfs，这样可以把子树状态转移到当前节点的状态。dfs结束后，由于 $xx$ 点是必须遍历到的，所以 $xx$ 周围的一定不能选，只需要统计对应的 $dp[i][0]dp[i][0]$ 即可。

#include<bits/stdc++.h>
using namespace std;
int dp[501010][2];
vector<int>g[505050];

void dfs(int x,int pr){
    int i;
    int sum1=0,sum0=0;
    for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            
            dfs(g[x][i],x);
            sum1+=dp[g[x][i]][0];
            sum0+=max(dp[g[x][i]][0],dp[g[x][i]][1]);
        }
    }
    dp[x][1]=sum1+1;
    dp[x][0]=sum0;
    
}
int main(){
    int n,i,x;
    cin>>n>>x;
    for(i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    dp[x][1]=1;
    dp[x][0]=-1e9;
    dfs(x,-1);
    int res=1;
    for(i=0;i<g[x].size();i++){
        res+=dp[g[x][i]][0];
    }
    cout<<res;
    
}