旅游

题解：

分析一下题目的每次操作，其实就是u节点选后，与其相连的点 都不能在选，然后要求选择最多的点，那么这就是一个树的最大独立集问题，我们用得dp[][]解决，并且由于题目要求S点必须选择，那么我们将点S设为根够
令dp[i][0]表示i节点不选时，以i为根的子树的最大独立集，dp[i][1]则为选时，则有

代码：

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const  ll inf  = 0x3f3f3f3f3f3f3f3f;
const int mod  = 1e9+7;
const int maxn = 5e5 + 4;
const int N    = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1);
ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}

int n,s,dp[maxn][2];
VI G[maxn];
void dfs(int u,int fa) {
    dp[u][0]=0;dp[u][1]=1;
    for(int v:G[u]) if(v!=fa) {
        dfs(v,u);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
int main() {
    //freopen("RACE input.in","r",stdin);
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++) {
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    dfs(s,-1);
    printf("%d\n",dp[s][1]);
}