Karashi

题解

树链剖分(2) 补题记(5)

/ 注册

全部文章 / 题解（共7篇）

树上行走

题7 - 树上行走最近做到的牛客挑战赛57的C题，我拿来分析一下题目要求两个操作：给定 x,y，令 x→y 的最短路上的点构成的点序列为 p，对于所有 i>1，令 b[ p[i] ] 增加 a[ p[i-1] ] 给定 x，输出 b[x] 的值。很明显的树链操作，对于 x ...

树链剖分

2022-02-24

1 607

小沙的身法

题6 - 小沙的身法寒假训练营2的一道题给定一棵树的路径关系，每个结点有一个高度，从低到高需要花费它俩高度之差的体力。有m个询问，每次询问从 x 到 y 结点需要花费多少体力（刚开始在地面，需要从地面上到结点x）。思路：因为没有修改操作，直接前缀和即可（ max(0,差值) 的前缀和）。做df...

树链剖分

2022-02-24

0 480

[JLOI2014]松鼠的新家

题5 - [JLOI2014]松鼠的新家给定一棵树的路径关系，给定一个访问结点的顺序序列a，先去a1，再去a2，……，最后到an。同时每经过一次结点，结点权值+1，对于最后一个访问的结点不用+1。最后询问每一个结点的权值。思路：对于从x结点去y结点，只需将x到y的链上权值+1，同时对y结点权值-...

树链剖分

2022-02-24

1 487

软件包管理器

题4 - 软件包管理器题目比较冗长，概括一下就是支持两种操作： 1、将 x 到根节点的链上权值改为1 2、将以 x 为根节点的子树中结点权值改为0 在每次操作后询问具体更改了几个权值（0改为0或1改为1不算）思路：理解题目意思后就会发现，还是一道模板题代码： #include<bits/...

树链剖分

2022-02-24

0 446

树上路径

题3 - 树上路径题目支持3种操作 1.将以u为根的子树内节点(包括u)的权值加val 2.将(u, v)路径上的节点权值加val 3.询问(u, v)路径上节点的权值两两相乘的和思路：很明显，唯一有难度的就是操作3。我们换位思考，要计算一个数组内元素两两相乘之和，其实就等于（元素之和的平方-...

树链剖分

2022-02-24

0 394

[HAOI2015]树上操作

题2 - [HAOI2015]树上操作题目支持3种操作：操作 1 ：把某个节点 x 的点权增加 a 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和思路：树链剖分模板题。（a可以是负数，我线段树的板子一直都是tag>...

树链剖分

2022-02-24

0 510

[LNOI2014]LCA

题1 - [LNOI2014]LCA 题目支持q个询问[l,r]中的结点与z结点的lca的深度之和，即∑l≤i≤rdeep[LCA(i,z)] \sum_{l≤i≤r} deep[LCA(i,z)]∑l≤i≤rdeep[LCA(i,z)] 思路：很明显，在1≤n≤50000,1≤m≤50000的条...

树链剖分

2022-02-24

0 349