今天早上七点起来尼玛OJ还是上不去先把题解写了来吧qwq，代码什么的OJ上不去放不了
A题我只能直接口胡了，赛场上打的暴力（话说好像随机数据树的高度期望只有 $O(logn)$？。只要一个点被标记，我们将它与它的父亲节点分裂。因为它的所有子树的节点（包括这个节点本身）到根节点上的路径最近的被标记节点，最远也就是这个点，不会再往上了。而这个点被标记了对除了自己子树以外的子树又没有任何影响，所以口胡出来是可以这样干的。
然后继续瞎yy。如果真的要硬写一个分裂，能用得上的并且能保证时间复杂度的我学过的数据结构大概只有不能路径压缩的并查集。不能路径压缩，显然会被特殊构造的数据（比如一条链）卡成 $O(N^2)$，而且和暴力也没啥区别。至少对于这道题，啥JB启发式合并根本没用只能通过路径压缩保证复杂度。
众所周知，路径压缩的并查集本来就不支持 split操作，只支持merge操作。而并查集的常见套路就是，只要一道题没有强制在线，那么离线倒着处理每个询问，将分裂转化为合并。
对于这道题，显然先要把原始的树构建好，记 $F_i$ 表示 $i$ 原来的父亲，$fa_i$ 表示并查集中 $i$ 的父亲。我们先对于所有的标记操作，把并查集挨个分裂。这里的 $O(1)$ 分裂不影响查询复杂度，等会儿反正要路径压缩。这道题的merge相比一般的merge不一样，比如标记了 $i$ 点，因为我们倒序处理每个询问，那么在这个当前标记操作之前的询问，$i$ 都没有被标记，也就是 $i$ 没有被分裂，因此将 $i$ 与 $i$ 在原始的树上的父亲节点何必，直接一句 $fa_i=F_i$。
由于这题是我原地瞎yy的，可能有问题，我自己都WA0
B题。首先考虑一个结论，最后留下的图一定是联通的。这个结论非常显然，只要删除了 $u\rightarrow v$ 这条边使得图不连通，那么这条边即使不删，不仅花费小，而且不会构成新的环。一个联通图，只有一个环，那么它其实就是 $n$ 个点 $n$ 条边，也就是树多了一条边构成环。当然这个图本身就是树的情况答案肯定就是 $0$ 了。
这种树多了一条边，构成一个唯一的简单环的图你谷日报上称之为奇环树，虽然我完全不会但是对做这个题没有影响。题目要求删的边边权尽量小，也就是留下的边边权尽量大，也就是把最大生成树变成了最大生成奇环树。
由于 Kruskal 可拓展性很强其实是因为我早就忘了Prim怎么写我采用Kruskal。将边按边权从大到小排序，如果遇到当前边，它不是一条重边且选择它就能构成环，并且当前没有选任何一条使整个图产生环的边，那么选择这条边，然后剩下的就和Kruskal没啥区别了。
至于怎么证明，我一个朴素的Kruskal板子都不会证的蒟蒻会证这个玩意儿吗，自己找kruskal本人去
老实说，学校OJ上不去，C题是啥来着
D题又是啥啊
哦想起来D了，md wtcl题都记不住，这个题一看数据规模就知道是贪心做法了。对于排序后的数组，$a_i+b_j$ 这个组合，一定存在 $i\times j - 1$ 种组合小于等于它。由于我们只关心它的值不关心它具体选哪两个数加起来，所以只要 $i\times j-1\ge n$，也就是 $i\times j> n$，这个组合显然不会是前 $n$ 小的。
所以我们枚举 $i$，$j$ 只用循环到 $n\div i$ 即可。看似只对内层 $j$ 的循环做了一个小小的剪枝，实际上，众所周知 $\sum\limits^{i\le n}_{i=1}\frac{n}{i}\approx nlog_2n$。所以我们其实只会考虑 $O(nlogn)$ 个元素。那么，这 $O(nlogn)$ 个元素如果排个序在输出就是 $O(nlognlogn)$ 的复杂度，对于1e6的数据很虚。虽然我比赛时由于太懒确实是这样艹过去的（这道题计算总用时，其实后面几个点都跑了超过1000ms），但是建议线性建队，不是说非要手写堆，NKOJ默认O2 STL性能飞起，所以也可以用<algorithm>自带的make_heap，pop_heap，push_heap函数。用法自行百度。这样做时间复杂度就是 $O(nlogn)$ 了，更严谨的是 $O(nlog_2(log_2n))$，不过影响不大。