kruskal重构树?
查看原帖
kruskal重构树?
426187
Ailuomangacencei楼主2023/11/11 18:22

这道题一眼丁真,是kruskal重构树

通过kruskal建立最大树的特殊性质 我们得知i,j最短边是lca(i,j)

还有就是这棵树上父节点大于子节点(前提是边权)

然后只需向上爬直到节点小于K即可

答案就是最后一个大于等于K节点的节点u的子树大小(sz[u] + 1) / 2.

不知道我说的对不对,大家可以帮忙指出我的错误

2023/11/11 18:22
加载中...