[JSOI2016]轻重路径[树链剖分]

时间:2022-11-09 20:27:22

题意

题目链接

分析

  • 先对原树树剖,在一次删点操作后从根节点开始二分,如果一条边从重边变成轻边,必然有 \(size_u\le \frac{1}{2}size_{rt}\) (取等号是特判对应儿子消失),二分后,将这个位置作为顶端递归寻找。容易发现这样操作的次数 \(< logn\) 次。
  • 判定一条边是否从重边变成轻边的依据是父亲的重儿子之前指向 \(u\) ,同时删除节点后有 \(size_u +1 =size_{another\_son}\),注意特判 \(u\) 是父亲子树最后一个节点的情况。
  • 时间复杂度 \(O(nlog^2n)\)

代码

代码链接

[JSOI2016]轻重路径[树链剖分]的更多相关文章

  1. 洛谷 P3384 【模板】树链剖分-树链剖分&lpar;点权&rpar;&lpar;路径节点更新、路径求和、子树节点更新、子树求和&rpar;模板-备注结合一下以前写的题目,懒得写很详细的注释

    P3384 [模板]树链剖分 题目描述 如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节 ...

  2. POJ 3237&period;Tree -树链剖分&lpar;边权&rpar;&lpar;边值更新、路径边权最值、区间标记&rpar;贴个板子备忘

    Tree Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 12247   Accepted: 3151 Descriptio ...

  3. &lbrack;BZOJ1576&rsqb; &lbrack;BZOJ3694&rsqb; &lbrack;USACO2009Jan&rsqb; 安全路径&lpar;最短路径&plus;树链剖分&rpar;

    [BZOJ1576] [BZOJ3694] [USACO2009Jan] 安全路径(最短路径+树链剖分) 题面 BZOJ1576和BZOJ3694几乎一模一样,只是BZOJ3694直接给出了最短路树 ...

  4. 牛客练习赛26 E-树上路径 (树链剖分&plus;线段树)

    链接:https://ac.nowcoder.com/acm/contest/180/E 来源:牛客网 树上路径 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 262144K,其他语 ...

  5. POJ 3237 Tree &lpar;树链剖分 路径剖分 线段树的lazy标记&rpar;

    题目链接:http://poj.org/problem?id=3237 一棵有边权的树,有3种操作. 树链剖分+线段树lazy标记.lazy为0表示没更新区间或者区间更新了2的倍数次,1表示为更新,每 ...

  6. BZOJ 1036&colon; &lbrack;ZJOI2008&rsqb;树的统计Count &lbrack;树链剖分&rsqb;【学习笔记】

    1036: [ZJOI2008]树的统计Count Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 14302  Solved: 5779[Submit ...

  7. 树链剖分I 原理

    树链剖分(Heavy Light Decomposition, HLD)是一种将对[树上两点间的路径]上[边或点]的[修改与查询]转化到[序列]上来处理的方法. 目的:将树的边或点转化到一个线性结构( ...

  8. SPOJ 375 &lpar;树链剖分&plus;线段树&rpar;

    题意:一棵包含N 个结点的树,每条边都有一个权值,要求模拟两种操作:(1)改变某条边的权值,(2)询问U,V 之间的路径中权值最大的边. 思路:最近比赛总是看到有树链剖分的题目,就看了论文,做了这题, ...

  9. LOJ2269 &lbrack;SDOI2017&rsqb; 切树游戏 【FWT】【动态DP】【树链剖分】【线段树】

    题目分析: 好题.本来是一道好的非套路题,但是不凑巧的是当年有一位国家集训队员正好介绍了这个算法. 首先考虑静态的情况.这个的DP方程非常容易写出来. 接着可以注意到对于异或结果的计数可以看成一个FW ...

随机推荐

  1. nginx入门篇----功能特性

    1.nginx功能特性 可以作为http服务器或者反向代理服务器 能够快速响应静态页面(html)的请求 支持FastCGI.SSL.Virtual Host.URL Rewrite.HTTP.Gzi ...

  2. JavaScript-navigator&lowbar;userAgent-编写一段代码能够区分浏览器的主流和区分

    1 userAgent:包含浏览器名称和版本号的字符串 <!DOCTYPE html> <html> <head lang="en"> < ...

  3. ! cocos2d 同一个sprite的触控问题

    如果对一个A sprite添加触控,然后在一个场景中创建四个A的实例,那么1234逐个添加的话,只有最后一个会被点击到.其他的将不会响应.

  4. JCO事务管理

    /* * 标准对账单过账 * @account 标准对账单号 * @year 年度 */ public List<String> doAccountStatmentPost(String ...

  5. HDU 4463 Outlets (最小生成树)

    题意:给定n个点坐标,并且两个点已经连接,但是其他的都没有连接,但是要找出一条最短的路走过所有的点,并且路线最短. 析:这个想仔细想想,就是应该是最小生成树,把所有两点都可以连接的当作边,然后按最小生 ...

  6. Linux网络编程-----Socket地址API

    (1) 通用socket地址 socket网络编程接口中表示socket地址的是结构体sockaddr,其定义如下: #include<bits/socket.h> struct sock ...

  7. Oracle EBS-SQL &lpar;WIP-9&rpar;&colon;检查车间任务超发料&period;sql

    select WE.WIP_ENTITY_NAME                                  任务号,         MFG_LOOKUPS_WJS.MEANING      ...

  8. H面试程序(15): 冒泡排序法

    #include<stdio.h> #include<assert.h> void display(int * a, int n) { for(int i = 0; i &lt ...

  9. Linux(CentOs 7)系统重装笔记&lpar;一&rpar;

    参考文章: https://www.jb51.net/article/95263.htm https://blog.csdn.net/JackLiu16/article/details/7988182 ...

  10. 解决word2013老是打开未响应情况

    问题:自己装了word2013时,每次打开word或者工作时,老是出现一个圈圈,提示未反应,是否关闭程序这样的提示: 解决方法:文件->选项->高级->显示->禁用硬件加速,将 ...