Garland 思路 写法比较显然，dfs去判断，是否存在子树所有节点权值相加等于即可特判一下无法整除的情况和不存在至少两个节点满足上述条件的情况，直接输出答案就🆗了。 代码 /*
Author : lifehappy
*/
#include <bits/stdc++.h>
us
展开全文
可能就我写的比较麻烦...emmm菜的真实.我写了两个dfs,因为我不想写lca...acm带板子还是好..写完看了评论区,都比我短.思路就是dfs1找到第一个sum/3,dfs2找到第二个sum/3即可. //i<->ai ti a[i]=0的i为根节点
#include <bi
展开全文
分析 我们对于每个子树的答案是可以预先知道的 ，那么如果 那么一定无解。之后我们可以直接遍历整个树得到 的节点。那么当这样的节点个数超过 的时候，这个树就是合法的，输出两个非树根的节点就可以了。那么总的复杂度为 。 代码 #include<bits/stdc++.h>
usin
展开全文
Garland 题目大意 有一颗 个点的数，第 个点的权值为 ，让你剪掉其中两条边，使得最后得到的三个子树的全职和相等 分析 在 遍历的时候，统计一下子树的权值之和，只要权值之和为总权值的 就可以放到队列里，最后看队列的大小是否大于 ，如果小于 那么显然是无解的情况了，还有如果总权值不是
展开全文
题意 你有一颗个节点的树，每个节点有一个点权，现在要求将这一棵树拆为三棵子树，子树的权值之和相等。 思路 由于点权之和确定，那么每棵子树的权值之和就一定。那么我们只需要搜索，当当前记录的权值之和为所有点权值的三分之一时，记录下答案和答案个数。当答案个数小于时，输出 代码 #include<bi
展开全文
分析 首先我们考虑什么时候可能有解当整棵树的权值和为3的倍数时（显然 至于判断是否可以分成这三个等分时我们先考虑两次分割深度最大的那一次分出来等于答案的一定是它的子树 且我们知道，当一个子树权值和时我们必须要把它分出去否则它不可能存在于其他任何分区 所以我们每次遇到子树权值和等于的直接减去即可 代码
展开全文
题目描述 你有n个节点的一棵树，n的量级是1e6。后面存在n-1行，第i行代表第i个节点的父节点是谁，并且给出第i个节点的权值，父节点是0的节点就是根。现在需要你找出一种方案，把两条连接的边切断，把这棵树分成三颗树，并且三棵树的权值之和相等。是否存在这种切法。如果不存在的话，需要输出-1。 Solu
展开全文
Garland 题目地址: https://ac.nowcoder.com/acm/problem/111886 基本思路: 首先我们知道只要整棵树的温度总和是确定的,那么这个连通块的温度就也是确定的,考虑树形,令表示以为根的子树的温度总和,只要子树温度和等于,那么我们就将这棵子树断开,消去
展开全文
做法 1.删除掉两条边所以会分成相同的三部分 ---> 先判断树上的值是否能被3整除 2.求出三部分的值是什么 3.对树跑一边dfs，记录能分成这个值的边 4.如果由三部分则输出答案，否则输出 代码 #include <bits/stdc++.h>
using namespac
展开全文
动笔之前多想想可以节约很多时间 想象一下删掉某条边会会发生什么 就是把以为根的子树砍掉,此时满足子树内的权值是树的三分之一 但是砍掉时候,的祖先们就不能利用这些权值了,所以设置为0 就这样一遍回溯就可以解决 亏我还想了那么久......彩笔 #include <bits/stdc++.h>
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
