做题记录 26.1.20

szt100309 · 2026-01-20 20:58:37 · 个人记录

\textcolor{black}\odot P9531 [JOIST 2022] 复兴计划 / Reconstruction Project

显然每条边对一个区间产生贡献，因此考虑求出每条边 e_i 的贡献区间 [L_i,R_i]，初始所有 L_i=-\infty,R_i=+\infty

按 w 从大到小依次尝试加入每条边 e_i=(u,v,w)

若 u,v 不在同一连通块，则直接加入边

若 u,v 在同一连通块，找到目前生成树上 u 到 v 的链上边权最大的边 e_j，R_i=\lfloor\frac{w_i+w_j}2\rfloor，L_j=R_i+1

这一过程可以暴力或用 \text{LCT}

求出 L,R 后转化为若干次区间加一次函数，修改之后单点查询，容易处理

时间复杂度 O((n+m)\log n+m\log m+q)，若暴力查找树边则复杂度 O(nm+m\log m+q)

代码

参考