警示后人
查看原帖
警示后人
388651
5k_sync_closer楼主2023/5/29 11:08

如果你使用连续两遍 DFS 的方法确定重心以及以其为根的子树大小,即类似

X(v, u, s[v]), X(R, 0, s[v])

的写法,那么建点分树时,把 uu 子树到 uu 的贡献的树状数组开到 su+1s_u+1,把 uu 子树到 faufa_u 的贡献的树状数组开到 su+2s_u+2。

因为这个树状数组下标从 00 开始,所以修改 / 查询时要后移一位,变成从 11 开始。

则下标范围为 1∼maxdep+11\sim\text{maxdep}+1,vector 大小要开到 maxdep+2\text{maxdep}+2。

所以 uu 子树到 uu 的贡献的树状数组要开到 su+1s_u+1,uu 子树到 faufa_u 的贡献的树状数组要开到 su+2s_u+2

查询参数 xx 超过树状数组大小 pp 时,将 xx 与 pp 取 min⁡\min。

2023/5/29 11:08
加载中...