标签: 树链剖分

3 篇文章

P5220 特工的信息流 题解
题目链接 @GuidingStar 让我来做这道题目然后我就做了一下,结果因为一个愚蠢的错误调了一个小时代码…… 题意 给定一棵树,维护区间后缀积之和,支持单点修改。 解析 个人觉得没那么难想(嗯,搞死我的是细节)。 我们先考虑线段树上如何维护这个东西。我们可以在维护区间后缀积之和的同时维护一下区间积,然后合并的时候只需要将左区间后缀积之和乘上右区…
P1505 [国家集训队]旅游 题解
题目链接 题意 维护一棵树,支持区间求和,区间最大值,区间最小值,区间取反,单点修改。 解析 这是一道很好的树剖练手题,思维难度不高,代码存在一些细节,本题解主要来说明这一部分,也用来警醒自己做题目时需要注意细节,尽可能避免调代码调半天的情况。 边权转点权 在树剖的两边 dfs 过程中,第一遍可以将边权赋给边端点中深度较大的那一个,即儿子节点。我们…
树链剖分入门学习笔记
这个算法还是比较容易理解的,只是代码调的我有点崩溃(还不是我太蒻了),因此学习笔记写的会比较简单。 本博客参考:PoPoQQQ 的课件;ChinHhh 的博客; attack 的代码启发。 前置 知识点:DFS序、线段树。 然后是一些概念: 重儿子:一个节点的子节点中,$size$(即子树大小)最大的那个。; 轻儿子:非重儿子的子节点; 重边:一个…