热门标签
更多>
搜索结果
查询Tags标签： 重链，共有 5条记录-
树链剖分学习笔记
树链剖(pōu)分定义 树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。 树链剖分有多种形式，如重链剖分、长链剖分等，通常说的树链剖分指重链剖分。 重链剖分 首先给出一些定义：重子节点：所有子节点中子树大小最大的子节点轻子节点：除重子节点的其它子节…
2022/4/28 23:12:39 人评论 次浏览 -
【模拟赛】乌拉~~（重链剖分）
背景大家好，我是一名勇敢的俄罗斯士兵，我昨天正在打 CodeForces\tt CodeForcesCodeForces 呢，突然被拉去打仗了。我们已经突入基辅，但因为推进过于迅速，后勤补给未能补上，我们现在急需 143 元来购买一些吃的 一个能替代通信员的老兄来解密一下临时截获的乌克兰电报，…
2022/2/25 23:52:11 人评论 次浏览 -
dfs序与树链剖分
dfs序与树链剖分本文根据以下视频整理 链接 引子 先看一个题: 已知一棵树，每个节点包含一个权值，你需要设法实现以下操作操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有结点的值加上z 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有结点的值之和 操作3:…
2021/8/18 6:07:53 人评论 次浏览 -
dfs序与树链剖分
dfs序与树链剖分本文根据以下视频整理 链接 引子 先看一个题: 已知一棵树，每个节点包含一个权值，你需要设法实现以下操作操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有结点的值加上z 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有结点的值之和 操作3:…
2021/8/18 6:07:53 人评论 次浏览 -
[NOI2014] 购票
这题怎么大家都做过了/kk 感谢 Fz 的题解！ 首先这题有一个 DP 式子， \[f_i = d_i \times p_i + q_i +\min(-d_j\times p_i+f_j) \]明显是斜率优化的形式。 但对于 \(u\) 有贡献的只有离他较近的若干个祖先。 这里就有几个做法；点分 树剖，u 到某个祖先可以剖为 若干条重…
2021/5/23 10:28:56 人评论 次浏览
