2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2 [2023/07/23 20:13] coldwinds |
2023-2024:teams:ikun_is_coding:2023_牛客暑期多校训练营_2 [2023/07/23 20:14] (当前版本) coldwinds |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 由于点的数量为1e4，最坏情况有1e8条边，无法直接建图，可以用线段树优化建图。对给出的树进行树链剖分，将每条线路的路径转化为若干连续区间，再使用线段树优化对区间的连边(若区间[L,R]在线段树上用一个节点维护，则直接将边连到改节点，不需要连到叶节点)。优化过的图，点数为5n+m=6e4，边数为5n+m(1+logn)=2e5。 | 由于点的数量为1e4，最坏情况有1e8条边，无法直接建图，可以用线段树优化建图。对给出的树进行树链剖分，将每条线路的路径转化为若干连续区间，再使用线段树优化对区间的连边(若区间[L,R]在线段树上用一个节点维护，则直接将边连到改节点，不需要连到叶节点)。优化过的图，点数为5n+m=6e4，边数为5n+m(1+logn)=2e5。 | ||
| + | |||
| + | **AC代码** | ||
| <code> | <code> | ||
2023-2024/teams/ikun_is_coding/2023_牛客暑期多校训练营_2.1690114432.txt.gz · 最后更改: 2023/07/23 20:13 由 coldwinds
