Karashi

分类

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

/ 注册

TA的专栏 4篇文章 0人订阅

2022杭电多校题解（补题记）

4篇文章 467人学习

全部文章（共20篇）

[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

浅谈 - 树链剖分

浅谈 - 树链剖分前言：其实只是最近练了一些题后，总结一下下树链剖分，其实就是把一棵树拆成多条树链，而两点之间所访问的树链是logn量级，因此给了我们很大的操作空间而一棵树，根据dfn映射到数组上，一条树链就是数组上一段区间。因此我们可以用前缀和、线段树、树状数组等等进行区间操作，区间操作的...

C++ 线段树树链剖分

2022-02-24

1 361

初遇 - 树链剖分

树链剖分前言：树链剖分，久闻大名。从半年前了解到这个知识点，却一直拖到寒假才来学...emm，确实拖了挺久的。小小总结一下，每个父节点都有一个重儿子和若干轻儿子，从一个轻结点出发，一直沿着重儿子延伸下去，就是一条重链。因此，一颗树就被剖分成了若干重链与若干叶子结点。并且，每一条重链的头都是轻结...

C++ 线段树树链剖分

2022-02-22

2 409

2021ICPC上海站-补题

2021ICPC上海站-补题前言：打铁的第二站，思维太过僵硬，专业知识还不够深。赛中过了DEG，然后I题dp没想出来，罚坐4小时… 比赛链接：https://ac.nowcoder.com/acm/contest/24872 E题（签到·贪心）题意：从n个数中选m个，使其两两之间差值≥k 思路...

C++

2021-12-09

2 2455

题解 | #Eyjafjalla#

Emm... 照着标答写的码，再详细捋一遍题目大意：给了一个以 1 为根的有根树，儿子的权值小于父亲的权值。多次询问，病毒在节点爆发，可以向任何权值范围在的节点传播，求最多扩散了多少个节点。整体思路： 1、先让病毒向上传播到节点，满足节点的父节点权值。（这样可以确保病毒只会在以为根...

暑期多校多校9

2021-08-17

3 470

题解 | #牛客推荐系统开发之静态特征获取#

C题dp大法好没考虑太多存储代表第人代表第个棋子开了（1-N）表示在前个棋子里面选（0-15）表示四位二进制数，比如“1101”代表一、二、四号选了棋子，三号还没选棋子至此我们可以推出比如当总结下规律，简化代码，可以得到 dp[i][j]=dp[i-1][j...

牛客练习赛84

2021-06-12

7 447