小w、小j和小z

首先一个简单的事实是，两个人相撞当且仅当他们开始时的相对位置和结束时相对位置发生了交换。

假设现在我们有一个时间 $T$，我们要怎么保留尽可能多的人，使得所有人不发生相撞呢？

如果用 $(s,t)$ 来表示每个人初始和结尾的位置，这就等价于选出最多的人，使得 $s_1 > s_2$ 的时候有 $t_1 > t_2$，如果按照 $s$ 排序，容易看出，这其实就是一个最长上升序列。

既然现在我们已经会判断对于一个时间 $T$，最小的 $K$ 是多少了，我们只需要二分答案，就可以轻松地解决这个问题了。

小h的树

首先，我们先考虑一个较为简单的情况，即 $k=n$ 时的情形。

我们容易发现 $k=n$ 时，其实就是选择一个点作为起点，每次向相邻的点移动，遍历所有点的最小代价。

我们发现除了起点到终点那条链上的边只走了一次外，其他的边都经过了两次。

那么答案显然就是 $2\sum v_e-$ 最长链的长度。

我们考虑更一般化的情况。

我们相当于要寻找一个大小为 $k$ 的点集，然后最小化 $2\times$ 这 $k$ 个点虚树的总边长-这 $k$ 个点直径的长度。

首先易得这 $k$ 个点一定是一个联通子树。

因为我们只是要求最小值，我们可以直接枚举这个虚树的直径是哪一条，然后树上背包扩展出不在直径上的点。

这样暴力的做是 $O(n^4)$ 的，稍加优化就能做到 $O(n^3)$。

我们接下来考虑一个更优的解法。

令 $g[x][k]$ 表示 $x$ 的子树内选择了 $k$ 个点，并且这 $k$ 个点包含了 $x$，构成的虚树总边长的最小值。

$f_0[x][k]$ 表示 $x$ 的子树内选择了 $k$ 个点，并且这 $k$ 个点的直径有一端是 $x$，构成的虚树总边长的最小值 $\times 2-$ 直径的长度的最小值。

$f_1[x][k]$ 表示 $x$ 的子树内选择了 $k$ 个点，并且这 $k$ 个点的直径两端都不是 $x$，构成的虚树总边长的最小值 $\times 2-$ 直径的长度的最小值。

转移则直接按照定义转移即可。

这样的复杂度为 $\sum_i \sum_{j,fa(i)=fa(j)} size(i)\times size(j)$。

注意到任意两个点只会在他们的 lca 处贡献一次代价，所以总复杂度为 $O(n^2)$。

小x的城池

By C_SUNSHINE

我们采用线段树直接维护整个序列，每个节点代表一个区间，并在节点上记录：

区间内的答案:在区间内已经找到了更高的 B 的 A 的数目 $ans$

区间内有多少向左的道路和向右的道路 $d_0, d_1$

区间内能够到达左端点/右端点的人口为 $k(0 \leq k \leq 75)$ 的还未找到更高的 B 的 A 的数目 $HL_k, HR_k$

若存在则记录同时到达左右端点的还未找到更高的 B 的 A 城市的编号 $pos$ (最多有一个)

区间被整体取反时以上所有信息

接着考虑如何维护，其实只要考虑合并就可以了：

由于我们需要计算的只是能找到更高的 B 的 A 城市的数目，除了在两个孩子中的答案，只要考虑其中一个孩子中的 A 能在另一个孩子中找到更高的 B 的数目，而具体情况需要考虑中间的边的方向。

这里只考虑从左到右的方向，反之是对称的做法：

在线段树上查询出从右孩子左端点开始能到的最远位置，并统计出这段中人口数最大的B。

检查左孩子的 $HR$ 和 $pos$，更新答案。

若右孩子能从左端点直接走到右端点，用未找到更高的 $B$ 的 $HR$ 和 $pos$ 中的节点更新当前节点的 $HR$ 和 $pos$。

而对于翻转操作，我们只需要打标记就可以了，由于区间和区间被flip的信息是同时维护的，打标记和标记合并复杂度是 $O(1)$的。

注意更新的同时也要更新被反转的区间的信息。且更新的同时也需要用到查询。

时间复杂度 $O((n + Q \log n)(R + \log n))$，其中 $R=75$.