A - 集合题意每个点可以属于 A,B,C 三个集合中的一个用mmm对关于nnn个点的的边(x,y,z)(x,y,z)(x,y,z)表示x,yx,yx,y之间有长度为zzz的边。qqq次询问每次将点的集合修改或者查询x,yx,yx,y分别在给出的集合中边权最小值。50%n≤100,m≤10000,q≤20000n \le 100,m\le 10000,q\le 20000n≤100,m≤10000,q≤20000另外50%n,q≤105,m≤500000n,q \le 10^5,m\le 500000n,q≤105,m≤500000且无向图上任意两个点间至多能选出3条不相交的路径。这数据范围直接分讨。前 50%这是暴力分吧。修改操作直接修改查询操作暴力看每一条边就行了O(m×q)O(m\times q)O(m×q)。后 50%由于给出了一个性质肯定跟这个有关。画一下图加入xxx和yyy有 3 条不相交的路。一条路径上的点到除这个路径的点至少已经有 2 条不相交的路。发现赛时的后 50% 不会做每次修改一个点假如正常图没有问题菊花图就会炸。能不能优化一下呢注意到询问和点的度数大小相关。注意到根号能过考虑将点按照n\sqrt nn​分为 A 类点大于根号和 B 类点小于根号。对于 B 类点可以暴力修改开 6 个 set 来维护答案对于 A 类点点数不会超过n\sqrt nn​个可以对于每一个点记录一下与它相邻的点颜色为 A,B,C 分别的一个 set。查询直接先查当前答案的 set再枚举每个 B 类点查询答案。B - 单旋题意维护 5 种操作分别为在 splay 中插入一个点 x但不进行任何旋转操作。其余操作分别为输出最小最大值深度以及将其旋转到根节点或旋转后删除。q≤105q\le 10^5q≤105可以发现将最小值或最大值移到根节点其实整个树的形状没有多大改变。以最小值为例它不存在左儿子。一次操作其实相当于将它右儿子接到它父节点的左儿子上在把自己当作根节点右儿子原根节点左儿子为空。由于答案只用考虑深度所以观察一下操作使深度的变化情况。可以发现除了最小值这个子树以外其它深度都加111。假如知道了这些很容易想到可以先将原本的所有 key 值离散化后面操作其实就都可以在线段树上去做。但是加入点不能快速找到 fa这个可以利用 set 去维护。只用找到第一个比自己小的点判断它是否有右儿子没有直接插否则插入到右儿子的左儿子里在修改一下深度父子关系等。C - 世界树题意求一个nnn个点叶子节点相距最远的距离。要求任意一个点左右儿子深度差小于 2.n≤1010000n\le 10^{10000}n≤1010000构造了一颗树发现要是差的最大值为xxx的话需要13579…13579…13579…共x1x1x1个数。但是样例过不了。才发现看错题了。其实fifi−1fi−21f_if_{i-1}f_{i-2}1fi​fi−1​fi−2​1答案就是f2∗k1nf_{2*k1}nf2∗k1​n中max⁡k\max kmaxk。而这个呢类似之前一道叫九连环的题目可以压位高精度来写。