标签:数据结构-树链剖分

题意有一棵 $n(\le 3\times 10^5)$ 个点的树和 $m(\le 3\times 10^5)$ 条路径,可以把一条边的边权改为 $0$ ,求所有路径长度最大值的最小值。题解求最大的最小值,可以二分答案 $mid$ 。可以发现如果路径的长度 $> mid$ ,那么路径上一定有一条边要被修改。所以修改的这条边需要覆盖所有长度 $> mid$ 的路径,并且边权要 $\g...
题解 数据结构-树链剖分 图论-LCA 图论-树上差分
省选/NOI-
题意给出一个无向图,有下列操作:$(1,a,b)$ ,查询 $a\rightarrow b$ 路径上桥的数量$(0,a,b)$ ,删除边 $(a,b)$ 。保证无论航线如何被破坏,任意时刻任意两点都能够相互到达。其中点数 $N\le 30000$ ,边数 $M\le 100000$ ,操作数 $Q\le 40000$ 。题解显然,桥的数量就是缩完点后两点间的树上距离,动态询问树上距离显然就是...
题解 数据结构-树链剖分 图论-桥
省选/NOI-
题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问,求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ,询问数 $M\le 50000$ 。...
题解 数据结构-树链剖分 算法-差分
NOI/NOI+/CTSC
题意给出一棵树,定义 $\mathrm{dep}[i]$ 为 $i$ 的深度,$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(l r z)}$ 的询问,求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。其中点数 $N\le 50000$ ,询问数 $M\l...
题解 数据结构-树链剖分 算法-差分
NOI/NOI+/CTSC
题意一棵树,每个节点有权值和信仰值。旅行时只在与起点信仰相同的节点停留,并获得权值。有如下操作:单点修改信仰值单点修改权值查询 $(x,y)$ 路径上权值和查询 $(x,y)$ 路径上权值最大值其中节点数 $N\le 100000$ ,操作数 $M\le 100000$ ,宗教个数 $C\le 100000$ 。题解显然每个宗教需要单独维护,但每个宗教开个线段树空间要爆,所以用动态开点线段树...
这道题做法还是比较容易想到的,就是码量有点大。不严格次小生成树的思路就是先得到最小生成树,然后枚举每一条不在树里的边,找到所构成的环上权值最大的边替换掉。而这道题要求严格次小,那么权值最大的边就不能与枚举的边权值相同,如果相同就替换环上次大的边即可。我还是敲了树剖,对于最大和次大边我用pair来存,可能是STL的缘故不开O2只有90。在合并(线段树合并和lca两侧合并)时对最大和次大的处理如...
题解 图论-最小生成树 数据结构-树链剖分
省选/NOI-
题意给一棵有 $n$ 个节点的树,然后再连 $m$ 条不重合的附加边,可以删除一条树边和一条附加边,问有多少种删除方法可以使树断裂。题解显然,每次加一条边以后树上一定会形成环,这个环任意断附加边就可以形成树,而树上任意断一条边就可以使树断裂。但是有可能会形成很多有重叠部分的环,这样按照上述方法不一定可以让树断裂。所以我们可以对每一条树边 $i$ 记录包含它的环的个数 $f[i]$ ,然后进行...
题解 数据结构-树链剖分 图论-LCA
这道题应该是迄今为止我做的时间跨度最久的题,在2018.5.17第一次提交,直到今天(2019.1.26)才终于AC。题意就是给你一棵树,起初所有节点上的数是 $0$ ,对于每次操作 $(a,b,c)$ ,把 $a$ 和 $b$ 及之间的节点全部加上 $c$ ,最后输出每个节点上的数。其实题本身很简单,就是一道裸的树剖,但是有多组数据,所以一定要记得清空数组!!!需要被清空的数组:前向星的边...
题解 数据结构-树链剖分
省选/NOI-
第一次写树剖没看题解A题,发现题解洛谷题解区大佬里竟然没有一个做法一样的,实在是太激动了树剖学习:https://llf0703.com/p/shu-lian-pou-fen.html方法裸树剖,直接用线段树维护每一段区间中被标记的最深的节点就行了。先全部赋值为-1,然后向上传递时直接取两段中的最大值即可(因为越深的点dfs序越大)还有需要注意的是查询中在链上往上跳时只要找到了有标记的节点就...
题解 数据结构-树链剖分
提高+/省选-
作为一个上个月刚学完线段树的蒟蒻,看Splay又看不懂,便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了,便去花了一天学了一个Tarjan求LCA(然而后来发现并不怎么需要),然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。准备工作链表/链式前向星线段树/树状数组/Splay等可以维护一段数据的数据结构LCA (其实只涉及到一些思想,而且几乎用不...
笔记 数据结构-树链剖分
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2