题解：P13783 [eJOI 2022] Bounded Spanning Tree

zrl123456 · 2025-12-18 21:18:32 · 题解

:::::info[题目基本信息] 考察：树链剖分，线段树，ST 表，贪心（省选/NOI-）。
题目简介：

- 这 $m$ 条边的边权构成一个 $m$ 阶排列。 - $\forall i\in[1,m]$，第 $i$ 条边的边权不低于 $l_i$ 且不高于 $r_i$。 - 前 $n-1$ 条边构成原图的一棵最小生成树（保证前 $n-1$ 构成原图的一棵生成树）。现在请你给出任意一种赋边权的方式，或报告无解。数据范围： - $1\le t\le 10^5

1\le n-1\le m\le\sum m\le 5\times 10^5
\forall i\in[1,m],1\le u_i<v_i\le n
\forall i\in[1,m],1\le l_i\le r_i\le m
::::: 你先考虑 m=n-1 怎么做，也就是不考虑第三条限制条件。
这时你发现这个树没用了，考虑直接对答案的值域扫描线，设当前要决策 i 这个边权要赋给谁，这时我们需要在未选择边权的所有 i\in[l_j,r_j] 的 j 考虑，容易发现我们可以直接贪心选择 r_j 最小的 j 进行一个赋值，正确性显然，简单使用堆维护即可做到 \Theta(m\log m) 的时间复杂度。

现在要求 m\ne n-1，加上了第三条限制条件。
观察一下，这个条件可以等价于所有非树边的端点间的树边权最大值小于自身边权，也就是说所有非树边的端点间的树边都需要在这条非树边前决策，那么首先你要保证在加入堆的过程中这条非树边要晚于这些树边加入（可以令非树边的 l_i 和这些树边的 l_j 加 1 取 \max），同时也要晚于这些树边被决策（可以令树边的 r_j 和这条非树边的 r_i 减 1 取 \min），这两个简单使用树链剖分可以做到 \Theta(n+m\log^2 n) 的时间复杂度，过不了，考虑优化。

一个数和一堆数取 \max：
不要想麻烦了，这个可以直接预处理倍增数组然后跑倍增算即可，可以少一个 \log。
一堆树和一个数取 \min：
这个你可以将这些数从小到大排序，这样每一个线段树节点通过适当剪枝只会被记一次答案，可以少一个 \log（其实可以直接拍成一个序列进行操作，记一下每一个位置的后继和答案，优化成并查集的复杂度，我写麻烦了）。

这样就可以过了。
时间复杂度为 \Theta(m\log m)，空间复杂度为 \Theta(m)。

code