9.2 比赛总结

E 到 H。

T2

简单树上 DP。

T4

原题。

首先将一个操作拆成两个操作，每个操作加入 \((x,y,z),(x+1,y+1,z+2)\dots\)。

用堆（队列也行）模拟 kruskal 的过程，讨论一条边之后，将它的后继加入堆。

可以发现，如果一条边无法使用，则可以不加入它的后继，因为树上连接这两个点的路径上的边的边权都小于等于这条边，它们的后继都在堆里，则它们的后继会连接这条边的后继。

初始会加入 \(2m\) 条边，后面加入堆就要使用一条边，一共使用 \(n-1\) 条边，则时间复杂度 \(O(n\log n)\)。

T3

线段树维护矩阵转移 DP，时间复杂度 \(O(n\log nm^3)\)。

T1

• 方法 1：求每个点到一个关键点的最短距离和距离最短的关键点，对于边 \((u,v,w)\)，如果距离它们最短的关键点 \(f_u\ne f_v\)，则可以用 \(dis_u+dis_v+w\) 更新 \(f_u,f_v\) 的答案。时间复杂度 \(O(m\log m)\)。
• 方法 2：对每个点记录两个距离：最短距离，与最短距离来源不同的次短距离，如果边 \((u,v)\) 的来源 \(f_u=f_v\)，则用 \(u\) 更新第一个距离；否则可以更新两个距离，答案为关键点的第二个距离。时间复杂度 \(O(m\log m)\)，常数略大，SPFA 可过。

策略问题

不要试图 \(1\) 秒 \(O(n\log^2n)\) 过 \(5\times10^5\)，同样，\(3\times 10^5\) 对 \(O(n\sqrt n)\) 和 \(10^5\) 对 \(O(n\sqrt n \log n)\) 都比较危险。考试遇到这种情况可以考虑优化或者打破原来思路，实在没有思路观察算法会不会跑满，尽量优化常数。