利用题目中的数据构造出来一个向下的树。然后如果是在叶子节点的话毫无疑问就得叶子节点独自承受所需要的灯笼，如果不是叶子节点的话就得是递归回去的时候带来子树挂上了多少灯笼以及最小时间花费的节点是多少。这样如果叶子节点不够挂的时候就直接去挂那个最小的时间花费即可。
#include <
展开全文
题目描述 给出一个有个节点的一棵树，每个节点都有需要完成的任务数量，某个节点的任务完成数量等于全部子节点中完成数量的和，如果子节点完成数量的和依旧不够当前节点的任务，我们对于当前节点可以花费每个任务的金币进行补交任务，当然这个补交存在也可以在子节点中进行。问你，完成这个节点全部的任务最小的花费是多少
展开全文
题意
以p(父亲),c(需要挂的最少装饰物个数),t(挂一个装饰物需要的时间)的形式输入每一个树上的节点。
问满足每一个节点的装饰物需求最少需要多少时间
思路
对于叶子节点i，他上面至少悬挂c[i]个装饰物
对于其它节点j，如果他的子节点累计挂的装饰物已经大于等于c[j]，则什么都不用做，如果
展开全文
思路 不要想复杂就好了...贪心的选取子树中最小的那个,多了就不要选,少了就更新数量...一个dfs就可以解决了.. 代码 #include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long
展开全文
题号 NC24623名称 Tree Decoration来源 USACO 题目描述 给你一棵有根树，根节点为1，第i个节点有ci，ti两个值ci表示以第i个节点为根节点的子树装饰物的数量至少为ci，ti表示往第i个节点挂上一个装饰物需要ti的时间，问在满足所有ci的条件下，最少的花费时间是多少？ 样
展开全文
解析
题目要求在满足子树装饰物数量的情况下，求花费时间的最小值，首先用邻接表存下各根节点的子节点，dfs遍历树，用一个数组吧维护每个子树的每个节点中花费时间最少的那个，dfs返回子树已有的装饰物数，若小于更节点则更新，并加入答案
#include<bits/stdc++.h>
using
展开全文
思路 叶结点只能挂在叶结点上，而父结点可以挂在父结点上也可以挂在叶结点上 所以优先从叶结点开始挂装饰品，利用叶结点的花费来更新父结点的花费，并记录该父结点下的叶结点装饰品的数量 代码 // Problem: Tree Decoration
// Contest: NowCoder
// URL:
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
