做题记录 25.9.4

· · 个人记录

\textcolor{black}\odot AT_arc181_e [ARC181E] Min and Max at the edge

分别考虑 \forall p\in\text{path}(u,v),p\ge u 和 \forall p\in\text{path}(u,v),p\le v 的限制，考虑通过一定方式给边赋权，使得满足要求的生成树必然为最小生成树

设边 (u,v) 赋为 w(u,v)，假定边权互不相同以保证 \text{MST} 唯一，且满足 w(u,v)=w(v,u)

在最小生成树中，对于一条非树边 (u,v)，任意 u-v 在树上对应的路径上的边 (u',v')，必有 w(u',v')<w(u,v)

原生成树的要求为 u\le u',v'\le v，因此限制 w 满足区间单调性，即 \forall [u',v']\subset[u,v],w(u',v')<w(u,v)

显然在此情况下合法的生成树必然为 \text{MST}

由此得到一个 O(m(n+m)\log n) 的算法：枚举每条边删去，求出剩余部分的 \text{MST}，若得到的生成树满足题目要求则边合法

发现求出 \text{MST} 后检测的方式很难优化

由于边权互不相同的情况下 \text{MST} 唯一，从而要么唯一存在合法的生成树，要么不存在

考虑在满足区间单调性的情况下，尽量选择 v 最大的（赋为 (n+1)v-u），尽量选择 u 最小的（赋为 (n+1)(n-u+1)-(n-v+1)），得到两颗生成树，若两者相同，则说明得到唯一且合法解

转化为给定一张图，对于每条边，求出删去它后对 \text{MST} 的影响（显然影响为 O(1) 的，因此可以加入初始 \text{MST}，枚举每条边作用修改，判断是否相同，然后撤销）

总时间复杂度 O(m\log m)，需要特判初始不连通的情况

代码

参考