加训一下。
1. [ARC181E] Min and Max at the edge
场上没人过的神题。（大概是搬运的官方题解）
先考虑如何 chk 一个图是否存在好生成树。观察好生成树的限制，发现其对于非树边的限制是在生成树上连接两点的路径有关。而 Kruskal 的证明就是对于每条非树边，其边权大于所有其路径上的树边，两者很像。
但是题目中的限制是点的限制，转到边上的想法是给点赋点权 \(X_i\)，然后 \((u,v)\) 的边权为 \(|X_u-X_v|\)。考虑把 \(X\) 设成一个递增的序列，比如 \(X_i=10^i\)，这样边权一定互不相同。
对于一棵好的生成树，设 \(S(u,v)\) 表示 \(u,v\) 之间的树上路径，则对于点 \(i\) 要求 \(\forall i\in S(u,v),X_u\leq X_i\leq X_v\)。而对于边 \((x,y)\)，\(X_u\leq X_x,X_y\leq X_v\)。设其根据上述定义的边权是 \(w(x,y)=|X_x-X_y|\)，则 \(\forall (x,y)\in S(u,v),w(x,y)<w(u,v)\)。这就证明了好的生成树一定是新图中的最小生成树。
因为可以构造出边权互不相同的情况，所以这也证明了好的生成树也是唯一的。跑出来这个图的最小生成树之后，检查每条非树边，如果都满足限制则该图是好的。
但是题目有多次询问，而且这个最小生成树也不是那么好求。不难发现其实图中定义的边权只需要满足 \(\forall i<j<k,w(i,j)<w(i,k)\) 并且 \(\forall i<j<k,w(i,k)>w(j,k)\) ，即满足区间包含单调性即可。
所以可以把边 \(w(u,v)\) 赋为 \(v\times(n+1)-u\)，这样得到的生成树一定满足对于任意非树边 \((u,v)\)，其路径上的最大值就是 \(v\)。原因是非树边 \((u,v)\) 路径上的边权应当都小于 \(w(u,v)\)，所以如果存在大于 \(v\) 的点则一定不合法。而且因为是 \(-u\)，所以合并两个连通块的时候，一边选择的较小的点会尽可能的大，这也满足路径上的最小值尽量是 \(u\)。
但是这样还是需要 chk 路径上点的最小值是否满足条件。可以再反着做一遍，\(w(u,v)=(n-u+1)\times(n+1)-(n-v+1)\)，同理得这样求出来的东西的最小值一定合法，最大值尽量合法。因为已经证明了好的生成树唯一，所以判一下两棵树是否相同即可。
这样就将问题转化成了比较好的形式：删边求最小生成树，可以看成是找一条非树边 \((x,y)\) 满足 \(x\in \text{subtree}(i),y\notin \text{subtree(i)},w(x,y)\) 最小。转成 dfn 序之后可以看成是两个 3-side 矩形查最小值，可以扫描线线段树维护，复杂度是 \(\mathcal O(n\log n)\)。
2. [ARC181F] Colorful Reversi
首先观察一下，对于 \(a,b,c,a\) 这种情况来说，两个 \(a\) 之间永远不可能发生操作。而 \(a,b,c,b,a\) 这种情况，两个 \(a\) 之间是有关联的。有一个很天才的想法是建树，一开始只有一个节点表示 \(a_1\)，维护一个指针 \(pos\) 表示当前在树上的哪个节点，接下来依次加入每个点 \(a_i\)：
- 若 \(pos\) 所在点的颜色和 \(a_i\) 相同，则 \(pos\) 不动。
- 否则若 \(pos\) 所在点有邻点的颜色是 \(a_i\)，则 \(pos\) 走向该邻点。
- 否则新建一个节点，颜色为 \(a_i\)，\(pos\) 走向该节点。
这样就得到了一棵操作树，它有一些很好的性质：
- 假设生成时在上面走过的路径是 \(B\)，则操作 \(l,r\) 等价于把 \(B[l,r]=\{x,y,y\dots y,y,x\}\) 变成 \(B[l,r]=\{x,x\dots x,x\}\)。
- 对于原序列，如果能够操作 \([l,r]\) 则 \(l,r\) 一定属于同一个点，否则 \(l,r\) 属于不同的点。
- 对于路径 \(\{v_1,v_2,v_3\dots v_k\}\)，通过操作将其变成 \(\{v'_1,v'_2,v'_3\dots v'_k\}\) 的最小代价是 \(\sum_{i=1}^k d(v_i,v'_i)\)，其中 \(d(x,y)\) 表示两点树上的距离。
接下来，对于 \(pos\) 的起始节点 \(x\) 和终止节点 \(y\)，最终序列的形态是若干个颜色段，而颜色恰好就是从 \(x\) 走到 \(y\) 所经过的简单路径上的颜色。证明很简单，显然路径上两个不同的颜色段永远无法合并，而如果存在其他的颜色则其两边的颜色一定是相同的，能再操作一次。
所以拉出树上 \(x,y\) 之间的路径，对于此路径外的部分一定会合并到路径上，可以先 dfs 一遍算出贡献，这样可以得到从 \(B\) 得到一个新的序列 \(C\)。接下来要解决问题的就是：现在有一个序列 \(C[1,n]\)，满足 \(\forall i<n,|C_i-C_{i+1}|\leq 1\)。现在要生成一个新的序列 \(C'\)，满足：
- \(C'_1=C_1,C'_n=C_n\)。
- \(\forall i<n,C'_{i+1}-C'_i\in[0,1]\)。
- \(\forall i<n\wedge C'_{i+1}=C’_i+1,C_i=C'_i,C_{i+1}=C'_{i+1}\)。
在此基础上满足 \(\sum_{i=1}^n |C_i-C'_i|\) 最小。设 \(f_{i}\) 表示考虑了 \(\leq i\) 的 \(C\)，\(C'_i=C_i\) 时代价的最小值，\(pre_i\) 表示 \(C_i\) 上一次出现的位置。转移比较简单：
\[f_i=\min \begin{cases} f_{i-1}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad C_i=C_{i-1}+1\\ f_{pre_i}+\sum_{j=pre_i}^{i}|C_i-C_j|\;\;\;\;\;pre_i\not=-1 \end{cases} \]因为 \(pre_i\) 是上一次出现的位置，所以对于所有的 \(j\) 要么 \(C_j\) 全部大于 \(C_i\)，要么全部小于 \(C_i\)，可以前缀和处理一下 \(\mathcal O(1)\) 转移。这样 \(f_n\) 加上之前把树缩成一条链的代价就是答案，复杂度是 \(\mathcal O(n)\) 或 \(\mathcal O(n\log n)\)。
标签：路径,困难,pos,生成,leq,quad,forall,一些 From： https://www.cnblogs.com/WrongAnswer90/p/18349631