Codeforces 587C Duff in the Army 题解
题意
给定一棵有$n$个结点的树,某些结点上有一些数,总共有$m$个数,有$q (1\le n,m,k\le 10^5)$次询问。
每次询问给定$u,v,a (1\le u,v\le n,1\le a\le10)$,求出 在$u$到$v$的路径上所有的结点上的数中,前$a$小的数(如果总数小于$a$,则输出所有的数)。
题解
在树中,从$u$到$v$的路径上,$a\le10$,从这三个条件可以想到用树链剖分,线段树中每个结点维护的是一个长度小于等于$10$的vector
,表示的是这些点中前$10$小的数,可以$O(1)$合并。
因为没有修改,所以省去了很多。程序也不是太难写。
时间复杂度$O(q\log n)$。
Tip: 可以用LCA,也是维护前$10$小的数,时间复杂度同样。
程序
1 | // #pragma GCC optimize(2) |