题解:
分析一下题目的每次操作,其实就是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]); }