网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P4216
2024-08-22
P4216[SCOI2015情报传递 树上主席树
题意:维护一棵树,某些点有点权(没有则为正无穷),点权为正整数,查询树上路径点权小于等于某个值的点的个数。分析:考虑维护主席树,root[i]数组存储第i个节点到根的点权的权值线段树的树根。更具体地,把第i个节点到根的路径上的点权累积到权值线段树中,对一个询问x,y,记lca为z,查询值为k,答案a