给出一颗大小为n的有树,选择一个包含1节点的联通块或者为空,要求联通块内的点权值和最大
考虑树形dp,从根节点开始,往叶子节点进行递归,为了确保不选择负贡献的子树节点,我们会对每个子树的权值和进行最大化,对于目前的节点,只把儿子节点是正贡献加进来即可 由于是树结构,使用 DFS 进行一次遍历,每个节点仅被访问一次,时间复杂度为 O(n),其中 n 为节点数,能很好地应对题目给定的约束
#include<bits/stdc++.h>
在一家创新企业中,员工之间形成树状的汇报关系,CEO 位于树的根节点,编号为 1。每位员工 i 有两个属性:创新值 xi 和执行值 yi。我们定义该员工的综合价值为 ci=xi+yi。
企业计划组建一个特殊的项目组。由于管理要求,如果某位员工被选入项目组,那么他的所有直属上级(包括 CEO)也必须被选入项目组。CEO 可以自己选择是否参加。项目组可以为空。
请问,在所有可能组建的项目组中,成员综合价值的总和最大是多少?
约束条件:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册