梵诗的技术博客

树上背包学习笔记 一、什么是树上背包？ 树上背包可以理解为：在树形 DP 的基础上，把多个儿子的子树状态逐个合并，得到当前节点的状态。 普通背包考虑的是物品的选择，而树上背包考虑的是如何把不同子树的状态合并起来。 一般分为三个步骤： 递归处理每个儿子。 枚举当前已经处理的部分和儿子子树的状态，进行背包合并。 更新当前子树的大小 siz[u]。 树上背包的核心是： 状态定义 + 初始化 + 枚举合并 + 更新子树大小。 二、状态定义 常见的状态定义： f[u][j] 表示以 u 为根的子树中，选择 j 个节点时的最优值。 根据题目不同，最优值可以是： 最大价值 最小代价 最大收益 方案数量 siz[u] 表示以 u 为根的子树包含的节点数量。 注意：状态定义需要根据题意确定，并不是所有树上 DP 都必须使用 siz[u]。 三、核心转移：j-k 与 j+k 两种写法本质相同，区别只是 j 的含义不同。 1. j-k 写法：先确定最终状态 12f[u][j]=max(f[u][j], f[u][j-k]+f[v][k]);...

Jobs through Pipelines 题意 给定 $n$ 个任务，第 $i$ 个任务的工作量为 $a_i$，这些任务依次进入一个有 $m$ 个阶段的流水线。 在处理之前，可以将序列的前 $t$ 个任务整体移动到末尾，相当于对原数组进行一次循环移位。 然后将得到的序列划分成不超过 $k$ 个非空连续段，每一段作为一个 batch。一个 batch 的工作量就是这一段所有任务工作量之和。 问如何选择循环移位方式以及分段方式，使所有任务完成的最早时间最小。 思路 一、先考虑固定的分段方式 假设最后被分成了若干个 batch，它们的工作量分别为： $$b_1,b_2,\cdots,b_s$$ 其中： $$\sum b_i=\sum a_i$$ 设： $$M=max⁡biM=\max b_i$$ 对于流水线： 第一批经过第 1 阶段需要 $b_1$； 后面的 batch 按顺序进入； 每个阶段之间会形成流水。 可以得到： $$\text{最终完成时间} = \sum b_i+(m-1)\max b_i$$ 而： $$b_i=\sum a_i$$ 是固定的。 所以原...

P3953 逛公园 - 洛谷 题意 给定一张 $N$ 个点 $M$ 条边的带权有向图（边权非负），起点为 $1$，终点为 $N$。设 $1 \to N$ 的最短路长度为 $d$。求总长度不超过 $d + K$ 的路径条数，答案对 $P$ 取模。若存在无穷多条满足条件的路径，输出 -1。 思路 刚拿到题目时，因为看到了“0 权边”和“无限多条合法路线”，很容易被引导到一个非常直观但在本题中行不通的方向上。下面我先分享一下我最初踩坑的思路，然后再推导出正确的解法。 一开始的错误思路：Tarjan 缩点 + DAG 上的最短路 看到图中可能有 0 权边构成的环，我的第一反应是：用 Tarjan 算法求强连通分量，把 0 权环缩成一个点： 用 Tarjan 算法跑出所有 SCC； 如果存在节点数 $>1$ 且边权和为 $0$ 的 SCC，就判定有 $0$ 权环，直接输出 -1； 将缩点后的 DAG 进行拓扑排序或 DP。 为什么这个思路彻底错了？ 粗暴判 -1 会导致严重误判：存在 0 权环就一定有无数条路线吗？并不是！如果这个 0 权环在一个根本无法到达终点...

P1600 天天爱跑步 - 洛谷 题意 给定一棵 $n$ 个节点的树，有 $m$ 个玩家在树上跑步。每个玩家从起点 $S_i$ 沿着最短路径跑到终点 $T_i$，每秒跑过一条边。每个节点 $u$ 上有一个观察员，他只会在特定的时间 $w_u$ 进行观察。问每个观察员能看到多少个刚好在那一秒跑到该节点的玩家。 思路 如果我们遍历每一个玩家到每一个的时间，那必然超时，比如换个思路，从观察员入手，看看那个玩家可以到达的时间刚刚好为 $w_u$ 本题的核心是：将任意一条树上路径 $S \to T$ 拆分为两段：上行路径 $S \to LCA$ 和 下行路径 $LCA \to T$。观察员位于节点 $u$，如果他能看到玩家，说明玩家到达 $u$ 的时间刚好为 $w_u$。 我们按上行和下行分类推导条件公式： 上行路径 ($S \to LCA$)： 点 $u$ 在 $S$ 到 $LCA$ 的路径上。玩家从 $S$ 走到 $u$ 的时间是 $dep[S] - dep[u]$。 满足条件的等式：$dep[S] - dep[u] = w[u] \implies dep[S] = w[u] + ...

Problem - 1029E - Codeforces 题意 给定一棵 $n$ 个节点的无根树）。你可以执行任意次操作：在根节点（1 号点）与任意其他节点之间添加一条边。 求最少需要添加多少条边，才能使得根节点到树上所有节点的距离都不超过 2。 思路 如果直接去想“怎么连边最优”，情况会非常复杂。 换个思路，你想啊，我们在 1 和 $u$ 之间连一条边，$u$ 到根的距离就变成了 1，那 $u$ 的儿子们到根的距离自然就变成 2 了。 也就是说：我们选一个点 $u$ 连边，它自己和它的直接儿子们就全部被“覆盖”了（距离 $\le 2$）。 树形 DP 状态设计 那么我们根据一个节点 $u$ 的覆盖来源，定义三个状态： f[u][0]：点 $u$ 被自己覆盖（自己选了）。 f[u][1]：点 $u$ 被儿子覆盖（自己不选，指望至少一个儿子选）。 f[u][2]：点 $u$ 被父亲覆盖（自己不选，儿子也不选，只能指望爹）。 转移方程 1. 当节点 $u$ 放置物品时（求 $f[u][0]$）： 既然 $u$ 已经放置了物品，那么它的所有儿子 $v$ 是否放置物品、是...

P3177 树上染色 - 洛谷 题意 有一棵 $n$ 个节点的树，树边有边权。你要从中选择 $m$ 个点染成黑色，其余 $n-m$ 个点染成白色。 求在所有的染色方案中，黑点两两之间的距离和 + 白点两两之间的距离和 的最大值。 思路 如果直接去算“黑点两两距离 + 白点两两距离”，由于要枚举点对，时间复杂度直接炸掉TTTLLLEEE。 用点不行，我们试试用边：考虑每一条边被经过了多少次 一、 核心思路：算每条边的贡献 对于树上的任意一条边 $(u, v)$（假设 $v$ 是 $u$ 的子节点），如果我们将这条边断开，树会被分成两部分： $v$ 的子树（假设大小为 $siz[v]$，其中有 $k$ 个黑点，则有 $siz[v] - k$ 个白点）。 树的其余部分（共有 $n - siz[v]$ 个点，其中有 $m - k$ 个黑点，其余 $(n - siz[v]) - (m - k)$ 个为白点）。 这条边会被哪些点对跨越并经过呢？ 黑点对：子树内的 $k$ 个黑点 $\times$ 子树外的 $(m - k)$ 个黑点。 白点对：子树内的 $(siz[v]...

P5588 小猪佩奇爬树 - 洛谷 题意 给定一棵 $n$ 个节点的树，每个节点有一种颜色，颜色编号在 $1 \sim n$ 之间。对于每一种颜色 $c$，问树上有多少条简单路径（即树上两点之间的路径）能够覆盖所有颜色为 $c$ 的节点。换句话说，对于每种颜色，我们需要统计有多少个无序点对 $(u,v)$，使得 $u$ 到 $v$ 的路径上包含了该颜色的全部节点。 思路 本题的核心是：对于每种颜色，判断其所有节点能否被同一条树上的简单路径覆盖，并统计这样的路径数量。 一个关键性质：树上的任意两点确定一条路径，而一条路径可以覆盖若干个点，当且仅当这些点在一条“链”上（即它们可以被同一条路径包含）。 因此，问题转化为： 对于颜色 $c$，判断它的所有节点是否位于同一条树上路径上，如果是，则统计有多少条路径能包含这条“最小覆盖路径”。 树上两点确定一条简单路径。对于一种颜色 $c$，设其所有节点构成的集合为 $S_c$。若存在一条路径覆盖 $S_c$ 中所有节点，则 $S_c$ 中深度最大的点一定是该路径的某个端点。以此为突破口，我们可以分类讨论。 由于 $|S_c|$ 的大小不...

#article-container { font-size: 16px; } 想给以后的自己留个念想，趁想着还记得，把大一写下来 从高中到大学 从高考结束，查分数，报志愿，查志愿。直到拿到录取通知书的那一刻，才发觉高中真的结束了， 马上要成为大学生了 不知不觉就开学军训了~ 完了，好像回忆写的有点晚了，已经有点模糊了。军训的时候只记得心里想着什么时候结束？什么时候结束？ 现在想想其实军训的时候是比较无忧无虑的，不用考虑别的，只要跟着训练就好。 部门与志愿 接下来你又加入了部门，做志愿活动的部门，认识了很多新的人，新的朋友。做了好多好多志愿，去敬老院，去东湖，去善行100……因为部门还参加了文艺汇演，看了十佳歌手的选拔，还有运动会去椒江玩的机会，一起去玩 偶尔你会感觉进入部门好累好累，但是不会后悔加入 迷茫与选择 在真正开始学习的差不多一个月，总是焦虑内耗的你，迎来了第1次的崩溃，你不知道大学到底要学些什么？到底该怎么学？我学他的意义是什么？学这到底有没有用？你开始怀疑，开始崩溃 你试图寻求帮助，于是找到了高中的班主任，希望他能给你一些建议，他也非常真诚的回复了你 你好...

P3976 旅游 - 洛谷 题意 给定一棵 n 个点的树，每个点有一个权值（宝石价格）。有 q 次操作，每次给出 a,b,v，表示从 a 到 b 的路径上所有点的权值都增加 v，然后输出这条路径上能获得的最大利润。 利润定义为：在路径上按从 a 到 b 的顺序，选择一个点买入，再在之后的一个点卖出，卖价减买价的最大值；如果最大值小于 0，则输出 0。 思路和代码 暴力 第一个暴力的想法就是：取出路径上a到b上所有点的权值，然后扫描维护最小值、最大差值来求出答案 需要取出路径a到b的点，我们需要找到lca，又因为这个题目需要动态修改权值，所以我使用了树链剖分+线段树 具体实现步骤 树链剖分预处理：依然使用树链剖分（HLD），将树映射到 DFS 序上，并实现 get_path(u, v) 函数，该函数能够把路径上的节点按实际行走顺序（从 u 到 v）收集到一个 vector<int> 中。 线段树：这个版本中的线段树非常简单，只维护区间和与懒标记，支持两种操作： 区间加（路径上所有节点加 v）。 单点查询（查询某个节点当前的权值）。 每次询问的处...

P4551 最长异或路径 - 洛谷 题意 给你一棵 带权树（每个边有一个权值），让你找到树上任意两个节点之间的路径，使得这条路径上所有边权的异或和（XOR）最大，并输出这个最大值。 思路 树上任意两点 u 和 v 之间路径的异或和，等于 u 到根节点的异或和 异或上 v 到根节点的异或和 Why？！  因为从根节点到 u，和从根节点到 v 的路径中，重复的部分（即从根节点到它们最近公共祖先 LCA 的那一段）会被异或两次。而根据异或的性质 a ^ a = 0，这一段就抵消掉了，剩下的正好是 u 到 v 的唯一路径。 操作：任选一个根（比如节点 1），跑一遍 DFS，计算出每个节点到根的异或值，存入数组 dis 中。 结果：问题成功从“树上找两条路径”降维成了“在数组 dis 中找两个数，使它们的异或值最大”。 转化后的经典问题（最大异或对）P10471 最大异或对 The XOR Largest Pair - 洛谷 现在你手里有一个数组 dis，里面全是整数。你需要找出 dis[i] ^ dis[j] 的最大值。 如果暴力枚举所有数对（O(n^2)），对于 n=100...