蓝桥杯 · 算法训练 · 结点选择—树形dp
不恰当的思路
首先拿到题,就想到 图染色——蓝桥杯 · 分考场 ,dfs 从第一个节点遍历到第n个节点,对于每一个节点试着去装进一个room(一个room内的所有人都没有直接关系),最后接收 room 内所有节点的权值和。事实证明,不仅空间耗费大,时间复杂度也很大(因为要便利每一种对于每一个节点装与不装的组合),拿下10分。
AC思路
又联想到另一道题 蓝桥杯 · 对局匹配 ,这个思路其实是对的,本题就是这题从线性转换为树型。
线性的 dp 动态方程就是 dp[x] = max(dp[x -> next], dp[x ->pre ->next] + w[x])。从起点走到当前结点的最大总权就是(该结点的子结点最大总权,和该结点的子子结点最大总权加上当前结点权值)的最大值,通俗来说就是取子结点 和 取当前结点加上子结点的子结点,哪个大。
树形dp的核心就是对于每一个结点,它的子结点个数是不定的,那么动态方程就是 取所有子结点的最大总权 和 取当前结点加上所有子子结点总权,哪个大。那么对于每个结点的最大总权和、所有子结点的最大总权怎么存储呢,dp[n][2]就可以了。dp[i][0]表示存储子结点的最大总权和,dp[i][1]表示存储当前结点最大总权和。
① dp[i][0] = sum( dp[i -> next][1] ) (i -> next表示i 结点的子结点)
② dp[i][1] = max(dp[i][0] , sum( dp[i -> next][0] ) + w[i] )
dfs递归搜索,dp 就从子节点往上推到根节点
AC代码:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
vector<int> E[maxn];
int w[maxn], dp[maxn][2];
int n,u,v;
void dfs(int pre,int x)
{
if(E[x].size() == 1 && E[x][0] == pre){ //走到最下面的节点了
dp[x][1] = w[x]; //当前节点最大总权为本身的权值
dp[x][0] = 0; //不存在后面的子节点,也就不存在和
return;
}
int cnt = 0;
for(int i=0; i<E[x].size(); i++)
{
if(pre == E[x][i]) continue; //这是来时的路
dfs(x,E[x][i]); //往子节点走,获取子节点的最大权值
dp[x][0] += dp[E[x][i]][1]; //dp方程 ①
cnt += dp[E[x][i]][0]; //dp方程 ②
}
dp[x][1] = max(dp[x][0],cnt+w[x]); //dp方程 ②
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&w[i]);
}
for(int i=1; i<n; i++)
{
scanf("%d%d",&u,&v);
E[u].push_back(v);
E[v].push_back(u);
}
memset(dp,0,sizeof(dp));
dfs(0,1);
printf("%d\n",dp[1][1]); //根节点就是全部最大
return 0;
}