BJOI 2013. 压力
∗†
张晴川
qzha536@aucklanduni.ac.nz
December 13, 2020
大意
给一个 N 个点,M 条边的无向图,并给出 Q 个点对。对于每个点对 (p, q),把
p 到 q 的所有路径中的必经点的权值加一。
求所有点的贡献。
数据范围
• N ≤ 10
5
• M, Q ≤ 2 × 10
5
题解
对无向图建广义圆方树,即每个点双加一个方点。对于每个点对,将路径上所
有点的权值加一即可,这一步可以用树剖。
注意事项:
1. Tarjan 求点双的时候需要把边放进栈中,而不是点。
2. 注意重边构成的点双。
复杂度
• 时间:O(N + Q log(N))
• 空间:O(N )
代码
https://gist.github.com/SamZhangQingChuan/5414a2d244df783723ad2dfb40c3be1e
∗
https://darkbzoj.tk/problem/3331
†
更多内容请访问:https://github.com/SamZhangQingChuan/Editorials
1
评论0