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

标签 LCA 下的文章

October 30, 2019

洛谷P1967 货车运输

题意多个询问,求两点间所有路径中最小边权的最大值数据范围:$0 < n < 10000,0 < m < 50000,0 < q < 30000,0 \le z \le 100000$题解求两点间所有路径中最小边权的最大值,可用$\mathrm{Kruskal}$重构树两点间所有路径中最小边权的最大值即为在重构树上其$\mathrm{LCA}$的点权注:可能...
October 22, 2019

洛谷P3938 斐波那契

题意求斐波那契堆的LCA数据范围:$a,b \le 10^{12}$题解性质:$f[i]$为$\le x$的最大斐波那契数,那么$x$的父亲节点为$x-f[i]$在此性质上让较大的跳到父节点,直到相等为止代码:#include<iostream> #include<cstdio> #include<algorithm> using namespace st...