描述
在一棵树上选择一些点,要求选择的点不相邻,问最多选多少点
思路
- 设表示以为根的子树且不选节点最多能选多少点,表示以为根的子树且选节点最多能选多少点,令树的根为,由于节点必须选,则答案为
- 转移方程为
代码
#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]);
}
时间复杂度,空间复杂度