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

标签 树链剖分 下的文章

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...
November 5, 2019

洛谷P4427/BJOI2018 求和

题意给出一棵树,$m$个询问,求从点$u$到点$v$的路径上所有节点深度的$k$次方和$\bmod \ 998244353$数据范围:$1 \le n,m \le 300000,1 \le k \le 50$题解对每一个$k$求一个树上前缀和答案为$$u+v-lca(u,v)-fa[lca(u,v)]$$代码:#include<iostream> #include<cstd...
November 5, 2019

洛谷P1505/国家集训队 旅游

题意给出一颗有边权的树,有$5$种操作:覆盖一条边的边权将$u$到$v$路径上的边权变为相反数询问$u$到$v$路径上的边权和询问$u$到$v$路径上的边权最大值询问$u$到$v$路径上的边权最小值数据范围:$n,m \le 20000$题解考虑将边权下放,随后此问题可用树链剖分解决线段树维护和,最大值,最小值及相反数标记区间处理的时候注意是否处理到$\text{LCA}$代码:#inclu...
November 4, 2019

洛谷P3313/SDOI2014 旅行

题意略数据范围:$n,q,c \le 10^5$题解由于要对每个宗教开一个线段树维护,空间过大,考虑动态开点线段树每颗线段树维护最大值以及区间和,对于修改操作,直接删除并新建节点之后在树剖上进行即可代码:#include<iostream> #include<cstdio> #include<algorithm> using namespace std; ...
October 29, 2019

洛谷P4315 月下“毛景树”

题意给出一颗有边权的树,有$4$种操作覆盖一条边的边权覆盖$u$到$v$路径上的边权增加$u$到$v$路径上的边权询问$u$到$v$路径上的边权最大值对于每个询问,输出答案数据范围:$1 \le n \le 100000$题解考虑将边权下放,随后此问题可用树链剖分解决注:由于边权下放,树上处理的最后一次(即在同一条链的情况下)需要将处理的左端点$+1$以避免处理到其$\mathrm{LCA}...
October 18, 2019

洛谷P3258/JLOI2014 松鼠的新家

题意树上操作$u$到$v$的路径上权值$+1$询问每个点的权值数据范围:$2 \le n \le 300000$题解树剖裸题注意每次的终点作为下次的起点,会多$+1$,记得$-1$;最后一次也是,题目有特殊要求代码:#include<iostream> #include<cstdio> using namespace std; #define ls rt<<...