洛谷4768 - [NOI2018]归程

真是纳闷,为什么这题在 BZOJ 上是权限题???

首先你需要了解一下 这种算法,然后你在重构树上树形 DP 处理出子树中距离的最小值,最后对于每次询问倍增找出最高点回答即可。

过程就不详细说啦,相信在坐的各位大佬早就会啦。。。

不过也有 sqq 这种巨佬写了可持久化并查集 AC 了的 QAQ ,下次写写。

倍增,处理出每个点往后 $2^i$ 的点、和、最大值,然后倍增乱搞即可。复杂度 $O(n log k)$ ,可过。

需要注意的是 $k$ 是 $10^{10}$ ,需要开 long long。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×