[AGC002D] Stamp Rally 题解
可以看做一道比较套路的的 $kruskal$ 重构树。
但或许也是一道复习与入门的好题。
思路
考虑把图论问题转化为树上问题。
发现所求的为路径上最大的最小。
容易想到 $kruskal$ 重构树。
发现由于从两端一起走，不能直接处理。
那么就可以在外面套一个二分，内部直接倍增处理即可。
Code
AC记录。
可以看做一道比较套路的的 $kruskal$ 重构树。
但或许也是一道复习与入门的好题。
考虑把图论问题转化为树上问题。
发现所求的为路径上最大的最小。
容易想到 $kruskal$ 重构树。
发现由于从两端一起走，不能直接处理。
那么就可以在外面套一个二分，内部直接倍增处理即可。
AC记录。