[SPOJ COT/BZOJ 2588]COT - Count on a tree(主席树,LCA,离散化)

发布于 2018-01-27  10 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[SPOJ COT/BZOJ 2588]COT - Count on a tree(主席树,LCA,离散化)

Description

You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.
We will ask you to perform the following operation:
u v k : ask for the kth minimum weight on the path from node u to node v

Http

SPOJ
BZOJ

Tag

主席树,LCA,离散化

题目大意

给出一棵点权树,求两点之间路径上的第\(K\)大的点权

解决思路

以\(1\)为根,变成有根树,那么现在就是查询\(u\)到\(lca\)并上\(v\)到\(lca\)路径上的第\(K\)大。考虑用主席树给每一个\(i\)到根的路径维护一棵权值线段树,那么可以用类似前缀和的思想,利用\(u,v,lca,fa[lca]\)这四个点加减构造出路径的权值线段树。
因为树是静态的,所以这里采用倍增的方式求出\(lca\)
注意离散化。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[SPOJ COT/BZOJ 2588]COT - Count on a tree(主席树,LCA,离散化)


HNCJ OIer 一枚