我口糊。
2026-01-13 20:53:49
发布于：广东
39阅读
0回复
0点赞
以下题目编号均为洛谷题目编号，即使 ACGO 有部分题目。
代码懒得打（
P2486
题意解析：给定一颗 个节点的树，每个点有一个颜色， 次操作：
- 将一个链上的所有点改成一个颜色。
- 查询一个链上的颜色段数量。
这真有紫吗。
注意到区间颜色段数量是可合并的，只需要处理出区间第一个颜色和最后一个颜色即可。
所以就可以树剖了。查询时注意顺序不能反了。
。
P3250
题意解析：给定一颗 个节点的树和一个空集合， 次操作：
- 在集合中添加一条 的路径，权值为 。
- 删除集合中的一个元素。
- 给出一个点 ，查询集合中不包括 的路径中最大权值。
我们可以将集合的内容改一下，改成不包含该路径的所有点。
由于一个路径可以转化成不超过 个编号区间，所以不包含这个路径的点也可以转化成不超过 个编号区间，证明显然。
然后再转化一下，发现只需要将每个点都看成一个集合，修改时在所有点上加入元素 ，查询时在对应点找最大值即可。
所以我们可以树剖再线段树套一个支持添加删除求最大值的数据结构，显然可以双堆小常数实现这个数据结构。（这一块看了题解）
。
P2680
题意解析：给定一颗 个节点的树，每条边有一个边权。再给定 条路径。你可以将任意一条边的边权变成 。求操作后这 条路径的长度最大值的最小值。
首先思考暴力怎么做。显然可以枚举每一条边，然后枚举每条路径，如果路径经过这条边，则将长度减去边权；否则不变，求最大值。这样是 的。
我们可以对每条边的答案拆分成“路径上包括这条边的长度最大值”与“路径中不包括这条边的长度最大值”。可以树剖完成。根据上面一题的结论，对于每条路径，我们只需要修改 个区间。最后枚举每条边求最小值即可。
。
有帮助，赞一个