首页 > 阔力梯的树
开通博客写题解
头像 lifehappy
发表于 2020-12-22 17:47:17
阔力梯的树 一般树上问题的求解有三种方法：点分治、树链剖分、。 这道题目中，结实程度是在子树上的定义，所以容易想到，所以我们可以考虑如何通过来维护子树信息。 如果使用来考虑求解，我们必然要涉及到点权插入到一个升序的数组中，考虑插入这个点之后，整体结实程度如何变化，大致分为一下几步。 一、第一个权值插 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2021-01-01 11:17:29
人都傻了 倒是模板,被的操作搞晕了... 返回一个大于等于查找元素的指针 是的末尾位置,但是最后一个元素在末尾位置的前面 当返回说明没找到这个元素 至于这里用也是有原因的,因为编号不重复,否则需要使用 回到这道题,维护每个点的结实度 显然想知道一个点的结实度必须要把所有子节点的编号排成一个序列计算 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CoolGuang!
发表于 2020-12-30 21:44:12
emmm.. 题意是计算每颗子树下，标号从小到大排列后，相邻项差值的平方和 涉及到静态子数问题， 就是经典解决方法了 维护了静态子数的信息，所以只需要处理新加入的权值 与 当前权值 的关系就好了 记得今年牛客2020多校有个三角形的加入边与删除边，维护最小差值的，与这个思路类似 首先把权值全部放入一 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”