uniHk

树链剖分

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 回文自动机(6) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章 / 树链剖分（共3篇）

树链剖分(洛谷P3384模板题)

题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1：格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2：格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和操作3：格式： 3 x z...

2020-01-02

0 501

旅行（树链剖分+动态开点）

旅行果然树剖的题代码量都不小，不过还是学了一波动态开点，妙呀！题意：给定一棵带权带颜色的树，两种操作+两种询问：操作1：更改某个点的颜***r> 操作2：更改某个点的权值询问1：询问 x ...

2020-01-02

0 429

【生物】分类（洛谷跨年夜场E题）（树换根+树剖）

【生物】分类这场比赛拿了个B题一血，舒服！题意：模板题给定一张连通图，求出以1为根的最小生成树（然后就跟图没啥关系了）。对于这棵生成树，有3种操作+3中询问：更换根节点树上 x ...

2020-01-02

0 675