A Training

相当于是要求保留的非树边和尽量大。

我们考虑所有边 $(u,v)$ ，如果距离为奇数，显然这条边必删。

如果距离为偶数，那么加入后会存在一个奇环。但是如果有两个相交的奇环，那么它们拼起来的大环的大小就是两个环长度和减去共有的部分乘二，这是个偶环。

所以我们相当于需要加入若干个点对，使得两两路径之间无交。

事实上这题还在 CERC 中出现过一个无权值的版本，那个问题由于路径权值是 $1$ ，可以证明局部最优等价于全局最优，因此 $dp$ 更加容易，但在这里行不通。

由于每个点度数不超过 $10$ 这可以考虑状压 $dp$ 解决。具体来说，设 $dp[u][s]$ 表示当前点为 $u$ ，某个儿子集合向这点的边已经被用掉了，此时子树选出的路径和的最大值。转移是非常显然的，我们只考虑这个点作为 $LCA$ 的路径，对每个路径分别考虑枚举一下子集去选择即可。

复杂度 $O(m2^d + nm)$

B Sequence

这题我场上想出了做法，可惜没有写完。。而且暴力的 MAXN 还开小了。。

我们考虑 恰好 $k$ 个段 这个问题看起来非常 WQS 二分。于是打个暴力输出一下，会发现答案真的关于选择的段数是凸的。

具体来说，这个可以被证明是一个费用流模型。如果没有非空的限制，那么我们可以从原点向 $i$ ，从 $i$ 向汇点连流量正无穷的边，然后 $i \to i +1$ 连流量为 $1$ 费用为 $v_i$ 的边。于是流量为 $k$ 的最大费用就是一个上凸的序列。然后考虑如果有非空的限制，那么在 $k$ 超过正数的个数之前，可以发现非空的限制是没有影响的，每次一定可以分裂一段。而如果 $k$ 超过了正数的个数，每次多选肯定是正好多选一个负数，因此这个题的答案就是一个上凸的序列，可以 WQS 二分。

我们考虑用线段树维护，对于一个节点，维护 在钦定这个点左右必选的时候，选 $i = 1\sim len$ 个段的最大收益。由于原问题上凸，显然可以说明 $dp$ 也是上凸的。因此合并的时候可以类似 DS1 的操作，枚举两边的情况，再枚举中间的合并情况，然后做 max+ 卷积。显然这个线段树的维护复杂度是 $O(n\log n)$ 的。

然后询问的时候分成了若干个线段树的区间。直接合并看起来不太行，于是考虑可以在外部二分，然后把区间都拖出来，形成一个长度为 $O(\log n)$ 的序列，然后再这个序列上再来做一次 $dp$ 。由于已经二分好了，对于一个段来说，在它是否钦定左右被选的时候的转移的系数就是确定的，这个系数可以通过在凸包上二分实现，这样我们就求出了序列的每个位置在二分出来的值固定时，这个序列是否钦定左右的时候最优的和是多少，然后可以直接 $dp$ 。

总复杂度 $O(n\log n + q\log v\log^2n)$ 。

C Archery

神题！

我们定义 $0$ 表示比你弱的人， $2$ 表示比你强的人，$1$ 表示你自己。

然后考虑用 $A,B$ 两个数组来维护上述过程。具体来说，我们钦定 $A$ 数组第 $i$ 个位置表示第 $i$ 个位置较强的人，钦定 $B_i$ 表示较弱的，特殊的，让第一个位置的 $A,B$ 反过来。

首先考虑 $O(n^2)$ 怎么解决问题，再去考虑优化。也就是说我们枚举你把自己放到哪里，然后尝试 $O(n)$ 判断一下。

于是每次操作就是把 $A$ 往前循环移动一次，然后调整这个 $A,B$ 。由于这题保证轮数大于 $2n$ （即使不保证也可以暴力跑一下前 $2n$ 轮），考虑这么多轮之后局面会变成什么样。

排名小于等于 $n + 1$

会发现，如果你的排名小于等于 $n + 1$ 最后肯定是 $B_1 = 2,B_{2 \sim n} = 0$ ，然后只是 $A$ 在不断地转，而且你也一定在跟着转。

于是我们考虑求出你在 $2n$ 轮之后第一次经过 $1$ 的时刻，此时一定已经进入循环，接下来的过程直接 $\mod n$ 即可知道最终位置。

但是这个东西如果真的要模拟 $2n$ 轮，复杂度仍然是 $O(n^2)$ 或者 $O(\frac{n^2}{\omega})$ 的。但是由于你只需要求出第一个位置当前的人是否是 $1$ ，如果去维护全局的信息看起来就很浪费。于是我们考虑去讨论一下第 $i$ 轮后进入 $1$ 的人是谁。

我们来分析一下这个东西。显然，第二轮进入第一个位置的人是 $2$ 号位置的最大的值。然后第三轮进入的人是 $2$ 位置的败者和 $3$ 位置的胜者中较大的，第四轮是之前未能进入的人和第四个位置的胜者中较大的。在此我们认定如果第 $i$ 轮在 $1$ 位置失败，就把这个人扔到 $i + n$ 这个位置。这样之后，就可以得出一个结论：第 $i$ 轮进入 $1$ 位置的，是之前还没进入的人再加入 $i + n$ 位置的人后最强的那一个。

因此我们可以用三个桶来维护这里说到的这些人。每次就是往桶里加入数以及拿出桶里最大的数即可。

然后模拟这个过程的复杂度就是 $O(n)$ 。

排名大于 $n + 1$

此时会发现 $0$ 是站不满空位的，于是你在 $2n$ 次操作之后一定是卡在一个地方动不了了。

也就是说我们只需要求出在 $2n$ 轮之后每个位置上的人是谁即可。不难发现对于一个场地 $i$ ，在 $j$ 轮后这个位置的人一定是这个位置原来的人再加上 $j$ 轮中进入这个位置的最菜的人。

也就是说，如果我们用之前的方法求出了在第 $x$ 轮进入场地 $i$ 的人，那么弹掉的人就是在前 $x+1$ 轮进入场地 $i - 1$ 的人。于是我们现在就可以求出在 $[1,n + 1]$ 轮的时候进入第 $n$ 个场地的人，然后用一样的办法求出在 $[1,n + 2]$ 轮进入场地 $n - 1$ 的人。多做几轮之后就可以求出每个位置在 $2n$ 轮后的人是谁。

具体做法和之前几乎一样，每次也是开三个桶记录三种人的个数每次再把当前位置的人拿出来，选择一个人留在这里，然后接着往前即可。

这样就可以 $O(n)$ 求出每个位置最后留下的人了。

然后我们就 $O(n^2)$ 解决了问题。考虑怎么优化。

我们考虑把这个序列循环丢到一个链上，具体来说，我们认为绕一圈回到的 $n$ 其实是 $n - n =0$ ，绕 $k$ 圈到达 $i$ 认为到达的地方是 $i - kn$ 。

我们考虑一个我证明不来的单调性，可以发现当你把起始位置向后移动的时候，最终到达的位置看起来也是会向后移动的。但是如果你向后移动导致多转了一圈，那么一定会导致最后位置也往前移动 $n$ 。

也就是说答案关于你选择的初始位置大概是这样的一个函数：它关于你选择的位置导致你需要转的圈数单调，如果圈数相同了，那么关于你选择的位置本身单调。

于是二分两次即可。复杂度就变成了 $O(n\log n)$ 。