第341场周赛 本场只有Q4有点意思，仅以此篇纪念我的LeetCode周赛AK。 Q4 最小化旅行的价格总和 2646. Minimize the Total Price of the Trips 现有一棵无向、无根的树，树中有 $n$ 个节点，按从 $0$ 到 $n - 1$ 编号。给你一个整数 $n$ 和一个长度为 $n - 1$ 的二维整数数组 $edges$ ...

腾讯音乐笔试 2023-04-13场 只能说，难度倒排也算是一种潮流了？🤮 第一题 规定一个好数组： 数组中的元素只有0，1，2； 数组中任意两个相邻的数字都不相同； 定义一个数组的权值是相邻两个数字的绝对值之和。例如数组1, 3, 2, 4, 1，则有权值为：$W = 3-1 + 2-3 ...

小红书笔试 2023-04-09场 第一题 给定一棵树$1 \dots n$（根节点未知），任意删去一条边形成了两棵树，求这两棵树节点数量之差的最小值，若有多个，统计同为最小值时能删边的方案数。 首先输入$n$表示节点数，随后$n-1$行每行分别输入$s$和$t$，表示节点$s$的父节点为$t$。 $1 \leq n \le 10^5$ 样例输入 3 # n 2 1 # ...

蚂蚁笔试 2023-04-04场 第一题 有$n$个人，分别是正直者H和欺诈者L，正直者只说真话而欺诈者只说假话。现在向其中一人$x$询问另一人$y$的身份，若是正直者则输出honester，否则输出liar，共计$q$次询问。 $1 \le n,q \le 10^4$ $1 \le x,y \le n$ $x \ne y$ 样例输入： 5 HLHHL 3 1 2 ...

树链剖分之重链剖分 参考 https://oi-wiki.org/graph/hld/ 介绍 重链剖分能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。可以用来： 修改 树上两点之间的路径上 所有点的值。 查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上...