题意
分析
- 先对原树树剖,在一次删点操作后从根节点开始二分,如果一条边从重边变成轻边,必然有 \(size_u\le \frac{1}{2}size_{rt}\) (取等号是特判对应儿子消失),二分后,将这个位置作为顶端递归寻找。容易发现这样操作的次数 \(< logn\) 次。
- 判定一条边是否从重边变成轻边的依据是父亲的重儿子之前指向 \(u\) ,同时删除节点后有 \(size_u +1 =size_{another\_son}\),注意特判 \(u\) 是父亲子树最后一个节点的情况。
- 时间复杂度 \(O(nlog^2n)\)
代码
[JSOI2016]轻重路径[树链剖分]的更多相关文章
-
洛谷 P3384 【模板】树链剖分-树链剖分(点权)(路径节点更新、路径求和、子树节点更新、子树求和)模板-备注结合一下以前写的题目,懒得写很详细的注释
P3384 [模板]树链剖分 题目描述 如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节 ...
-
POJ 3237.Tree -树链剖分(边权)(边值更新、路径边权最值、区间标记)贴个板子备忘
Tree Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 12247 Accepted: 3151 Descriptio ...
-
[BZOJ1576] [BZOJ3694] [USACO2009Jan] 安全路径(最短路径+树链剖分)
[BZOJ1576] [BZOJ3694] [USACO2009Jan] 安全路径(最短路径+树链剖分) 题面 BZOJ1576和BZOJ3694几乎一模一样,只是BZOJ3694直接给出了最短路树 ...
-
牛客练习赛26 E-树上路径 (树链剖分+线段树)
链接:https://ac.nowcoder.com/acm/contest/180/E 来源:牛客网 树上路径 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 262144K,其他语 ...
-
POJ 3237 Tree (树链剖分 路径剖分 线段树的lazy标记)
题目链接:http://poj.org/problem?id=3237 一棵有边权的树,有3种操作. 树链剖分+线段树lazy标记.lazy为0表示没更新区间或者区间更新了2的倍数次,1表示为更新,每 ...
-
BZOJ 1036: [ZJOI2008]树的统计Count [树链剖分]【学习笔记】
1036: [ZJOI2008]树的统计Count Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 14302 Solved: 5779[Submit ...
-
树链剖分I 原理
树链剖分(Heavy Light Decomposition, HLD)是一种将对[树上两点间的路径]上[边或点]的[修改与查询]转化到[序列]上来处理的方法. 目的:将树的边或点转化到一个线性结构( ...
-
SPOJ 375 (树链剖分+线段树)
题意:一棵包含N 个结点的树,每条边都有一个权值,要求模拟两种操作:(1)改变某条边的权值,(2)询问U,V 之间的路径中权值最大的边. 思路:最近比赛总是看到有树链剖分的题目,就看了论文,做了这题, ...
-
LOJ2269 [SDOI2017] 切树游戏 【FWT】【动态DP】【树链剖分】【线段树】
题目分析: 好题.本来是一道好的非套路题,但是不凑巧的是当年有一位国家集训队员正好介绍了这个算法. 首先考虑静态的情况.这个的DP方程非常容易写出来. 接着可以注意到对于异或结果的计数可以看成一个FW ...
随机推荐
-
nginx入门篇----功能特性
1.nginx功能特性 可以作为http服务器或者反向代理服务器 能够快速响应静态页面(html)的请求 支持FastCGI.SSL.Virtual Host.URL Rewrite.HTTP.Gzi ...
-
JavaScript-navigator_userAgent-编写一段代码能够区分浏览器的主流和区分
1 userAgent:包含浏览器名称和版本号的字符串 <!DOCTYPE html> <html> <head lang="en"> < ...
-
! cocos2d 同一个sprite的触控问题
如果对一个A sprite添加触控,然后在一个场景中创建四个A的实例,那么1234逐个添加的话,只有最后一个会被点击到.其他的将不会响应.
-
JCO事务管理
/* * 标准对账单过账 * @account 标准对账单号 * @year 年度 */ public List<String> doAccountStatmentPost(String ...
-
HDU 4463 Outlets (最小生成树)
题意:给定n个点坐标,并且两个点已经连接,但是其他的都没有连接,但是要找出一条最短的路走过所有的点,并且路线最短. 析:这个想仔细想想,就是应该是最小生成树,把所有两点都可以连接的当作边,然后按最小生 ...
-
Linux网络编程-----Socket地址API
(1) 通用socket地址 socket网络编程接口中表示socket地址的是结构体sockaddr,其定义如下: #include<bits/socket.h> struct sock ...
-
Oracle EBS-SQL (WIP-9):检查车间任务超发料.sql
select WE.WIP_ENTITY_NAME 任务号, MFG_LOOKUPS_WJS.MEANING ...
-
H面试程序(15): 冒泡排序法
#include<stdio.h> #include<assert.h> void display(int * a, int n) { for(int i = 0; i < ...
-
Linux(CentOs 7)系统重装笔记(一)
参考文章: https://www.jb51.net/article/95263.htm https://blog.csdn.net/JackLiu16/article/details/7988182 ...
-
解决word2013老是打开未响应情况
问题:自己装了word2013时,每次打开word或者工作时,老是出现一个圈圈,提示未反应,是否关闭程序这样的提示: 解决方法:文件->选项->高级->显示->禁用硬件加速,将 ...