BZOJ 2588 Spoj 10628. Count on a tree

发布于 2017-08-13  189 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2588

题意:强制在线树上路径第 k 小。


把每一个点到根的路径建主席树,这样查询一个路径 u->v 即相当于查询版本 u+v-lca(u,v)-fa[lca(u,v)]

最开始因为离散化去重的姿势苦恼好久... 突然发现不用去重...

 


一个非常弱的准退役OIER