梵诗的技术博客

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...

并查集解决的是这样一个标准问题：动态维护若干个不相交的集合，支持合并两个集合与查询两个元素是否属于同一集合。但在实际问题中，很少会直接给出“请合并集合”的题目。更多时候，我们需要先从题意中找到“连通关系”或“等价关系”，再判断题目究竟需要这种关系的什么信息。 因此，并查集题型可以沿着两条主线展开： 怎样识别并查集模型：对象是什么，什么算“连通”或“属于同一集合”； 怎样询问：求连通块数量、集合大小、判断是否成环、带权关系推断，还是扩展域的分类问题。 一、怎样从原问题中找到并查集模型 1. 显式的连通性问题 问题直接描述“连通”、“相连”、“属于同一组”等概念，是最直接的并查集应用场景。 典型例题：P1551 亲戚 给定 n 个人、m 对亲戚关系，以及 p 个询问，每次询问两个人是否为亲戚。亲戚关系具有传递性。 解法思路：每个人初始是一个独立的集合。每读入一对亲戚关系，就将两人所在的集合合并。查询时只需判断两人是否在同一集合中。 1234567891011121314151617181920212223242526272829303132const int maxn=5000+...

不知不觉19啦~~ 记录一下吧 时光倏忽而过，恍惚刚吹完十八岁的生日蜡烛，转眼便站在了十九岁的路口。 回望这一年，你成长了好多好多，从前的你会因为一次考试没有考好而崩溃落泪，会因为一些小事情反复陷入精神内耗，会因为别人的看法而伤心，现在呢，慢慢的你好像强大了起来，不会因为一点点小事就埋头痛哭，遇到事情不在依靠别人，而是自己慢慢尝试解决，解决了自己很多以前感觉不可能的事情，抗压能力真的强了好多好多。但是呢，其实你还是会因为未来而焦虑，还是会因为自己的选择而苦恼，你不知道自己的选择是不是正确的，只能在心里默默承受，纠结当下的选择对错，一遍遍劝慰自己：当下就是最好的。 这一年在忙碌充实又焦虑迷茫交织中度过，认识了好多朋友，遇到了很好很好的室友和朋友，收获了好多。这一年经历了高考，踏入崭新的大学校园，感觉整个人都不一样了。还去了好多好多地方玩，暑假和ysh去景德镇，买了好多好多东西。和家人去了马来西亚，第一次出国玩，很新奇的体验吧。寒假去了和cjj去了南昌，南昌拌粉还有瓦罐汤真的真的好好吃，也很好玩。去比赛浙江省省赛（虽然打铁了，但也是一次很好经历），在杭州和xxy见面吃饭。五一和大学朋...

P4180 严格次小生成树 - 洛谷 题意 要找一棵“严格大于最小生成树、且权值和最小”的生成树 思路 核心策略是“非树边替换树边”： 先用 Kruskal 算法求出最小生成树，记录其权值总和为 sum。 遍历每一条不在最小生成树中的非树边 $e(u, v, w)$。如果把这条边强行加到树中，树上就会形成一个环（即 $u$ 到 $v$ 的树上路径加上这条新边）。 为了重新变成一棵树，我们需要在这个环里删掉一条原本就在树上的边。 为了让新的树权值总和增加得最少（且严格大于 sum），我们需要在 $u$ 到 $v$ 的树上路径中，找到权值最大、且严格小于 $w$ 的那条树边替换掉。 我使用了Kruskal来求最小生成树，倍增lca来查找 $u$ 到 $v$ 的树上路径中的替换边 分块代码 看完思路后，我们一步一步来分块拆解代码 1.Kruskal 求最小生成树 123456789101112131415161718192021222324252627282930313233struct Edge{ int u,v,w; bool vis;//记录是不是树边...