夢に僕らで帆を張って
来るべき日のために夜を超え

标签 圆方树 下的文章

November 1, 2019

洛谷P4630/APIO2018 Duathlon 铁人两项

题意无向图中,求三元组$(s,c,f)$的个数,使得从$s \rightarrow v \rightarrow f$为简单路径数据范围:$n \le 100000,m \le 200000$题解可以发现,答案就是路径上可能经过的点数将图缩成圆方树,统计树上路径点数若将方点点权标为点双大小,圆点点权标为$-1$,则某条路径上的答案就是圆方树上两点之间的点权和因为枚举点对是$O(n^2)$的,所...