夢に僕らで帆を張って
来るべき日のために夜を超え

标签 主席树 下的文章

November 6, 2019

洛谷P2633 Count on a tree

题意给出一棵带点权的树,$m$个询问,求$u \rightarrow v$路径上第$k$小的点权数据范围:$n,m \le 100000$ [强制在线]题解树上静态区间第$k$小,使用主席树维护序列上的主席树使用的是前缀和思想;那么自然,在树上的情况就要用到树上前缀和建树的时候在其父节点的基础上拷贝包含$u \rightarrow v$路径上的信息的应为$$T[u]+T[v]-T[lca(u...