BZOJ 1803 Spoj1487 Query on a tree III

发布于 2017-07-02  129 次阅读


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

题意:给出一棵 n 个点的树,节点有点权,保证点权两两不同,m 次询问 x 的子树中权值第 k 小的节点编号。


主席树经典题,考虑区间第 k 小在序列上容易解决,现在在树上了。关于 dfs 序有一个性质,一个节点子树中的节点在一段连续的区间里,区间大小为子树大小。

证明是显然的,因为 dfs 的过程一定是搜完这个子树再去考虑外面的情况...

所以在 dfs 序列上建主席树即可啦... 惨遭多次题意杀...

 


一个非常弱的准退役OIER