首页 > Eyjafjalla
开通博客写题解
头像 不想喂饭
发表于 2021-08-14 20:48:51
赛中一直没有想明白，怎么向上查询到其他子树的满足条件数，于是一直在乱调其实，只需要向上倍增到满足符合的节点，然后从这个节点开始查询。大家伙好像用主席树用的比较多，（主席树还不太会...呜呜），这边讲一下线段树的做法首先，数显剖分将这颗树映射到数组中，简单的两个dfs，同时记录每个节点的前置节点，倍增 展开全文
去ta的博客 赞 (12) 回复(3) 收起
头像 Kur1su
发表于 2021-08-15 10:29:53
Description 给出一棵树， 个查询，每次查询给出 代表病毒在 点爆发，在 的温度可以传播根节点为 ，保证离根节点越近，温度越高，根节点温度最高。 Solution 我们知道，对于一个初始节点，它的子树必定温度小于它本身，所以设当前温度为 , 中 的这一部分可以直接查询子树里有多少 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 shyyhs
发表于 2021-08-16 15:35:11
= =两个月不学习的fw这两个月来写的第一个题..简单的来说就是树状数组硬搞...首先在假如温度区间不在这个范围的点,先做个标记,就不用往上跳,且下面的点也一定不行..然后就简单的倍增因为符合单调性就跳,跳到最高点然后判断子树中合法的.简单的说就是在这个温度区间的,然后因为不涉及修改操作,可以树状数 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 河南老乡唐可可
发表于 2021-08-22 17:57:12
题目大意 一个国家有个城市，由个道路彼此相连，构成一个树。其中首都（一号节点）紧挨着 艾 雅 法 拉 火山，所以温度最高，其它城市的温度是随着距离首都的距离而递减的（每条道路长度可以认为是相同的）。现在一种病毒在城市​爆发，它的可以存活的温度区间是​​。当有道路相连的两个城市温度都可以让病毒存活，且 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-09-07 17:17:45
E、Eyjafjalla 题目大意 你有一颗以111为根的n(1≤n≤105)n(1\le n\le 10^5)n(1≤n≤105)个节点的有根树，每个点都有一个温度ti(1≤ti≤109)t_i(1\le t_i\le 10^9)ti​(1≤ti​≤109)，并且保证每个父亲到儿子的温度一定是递减 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Karashi
发表于 2021-08-17 16:05:11
Emm... 照着标答写的码，再详细捋一遍 题目大意： 给了一个以 1 为根的有根树，儿子的权值小于父亲的权值。 多次询问，病毒在 节点爆发，可以向任何权值范围在 的节点传播，求最多扩散了多少个节点。 整体思路： 1、先让病毒向上传播到 节点，满足 节点的父节点权值。（这样可以确保病毒只会在以 为根 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 夏驰
发表于 2021-08-16 10:55:44
该解法时间复杂度为O(nlognlogn)。貌似很多大佬都用优秀的O(nlogn)就把题目解决了，这里提供一种时间复杂度并没那么优秀的解法（离线 + dsu on tree + 树状数组）。题意：n个火山形成一棵树，1号火山为根节点，每一个火山都有权值，t[i]表示第i座火山的温度。 对于从 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”