2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/29 10:25] jxm2001 [题解] |
2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/29 10:28] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 260: | 行 260: | ||
| $$ | $$ | ||
| - | 接下来考虑如何维护 $H$ 集合即可，将点权转移为到父结点的边权，发现可以类似虚树 $\text{dp}$ 的方式维护最小连通集合。 | + | 接下来考虑如何维护 $H$ 集合即可，将点权转移为到连向父结点的边权，发现可以用类似构建虚树 $\text{dp}$ 的方式维护最小连通集合。 |
| - | 另外由于本题建图的特殊性，导致 $\text{dfs}$ 序可以等于结点编号。 | + | 另外由于本题建树的特殊性，使得可以直接让 $\text{dfs}$ 等于结点编号。时间复杂度 $O(n\log n)$。 |
| - | + | ||
| - | 时间复杂度 $O(n\log n)$。 | + | |
| <hidden 查看代码> | <hidden 查看代码> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_706_div._1.1616984710.txt.gz · 最后更改: 2021/03/29 10:25 由 jxm2001
