描述

在一棵树上选择一些点，要求选择的点不相邻，问最多选多少点

思路

• 设$dp[i][0]dp[i][0]$表示以$ii$为根的子树且不选$ii$节点最多能选多少点，$dp[i][1]dp[i][1]$表示以$ii$为根的子树且选$ii$节点最多能选多少点，令树的根为$ss$，由于$ss$节点必须选，则答案为$dp[s][1]dp[s][1]$
• 转移方程为$\{\begin{array}{c}dp[i][1]={\sum }_{v\mathrm{是}i\mathrm{的}\mathrm{儿}\mathrm{子}}dp[v][0]\\ dp[i][0]={\sum }_{v\mathrm{是}i\mathrm{的}\mathrm{儿}\mathrm{子}}max(dp[v][0],dp[v][1])\end{array}\backslash begin\{cases\}dp[i][1]=\backslash sum\_\{v是i的儿子\}dp[v][0]\backslash \backslash dp[i][0]=\backslash sum\_\{v是i的儿子\}max(dp[v][0],dp[v][1])\backslash end\{cases\}$

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int dp[MAXN][2];
vector<int> E[MAXN];
void dfs(int now,int fa)
{
    dp[now][1]=1;
    for(int v:E[now])
    {
        if(v==fa)
            continue;
        dfs(v,now);
        dp[now][1]+=dp[v][0];
        dp[now][0]+=max(dp[v][0],dp[v][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);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(s,s);
    printf("%d\n",dp[s][1]);
}

时间复杂度$O(n)O(n)$,空间复杂度$O(n)O(n)$