重链剖分
重链剖分是一种以 \(O(\log^2 n)\) 时间复杂度维护树上路径,同时支持 dfs
序相关操作的算法。
基本定义
- 子树大小
sz[u]
:以 \(u\) 为根的子树中所含节点的数量; - 重儿子
son[u]
:节点 \(u\) 的所有儿子 \(v\) 中,sz[v]
最大的一个; - 重边:由一个非叶子节点指向其重儿子的边;
- 重链:由若干重边组成的连续的链;
算法原理
如果我们设定 dfs
的遍历顺序,使对于任意一个非叶子节点 \(u\),它的重儿子 son[u]
总是在所有儿子中最先被访问到。这样,一条重链上所有节点的 dfs
序一定是连续的。
我们可以使用线段树维护重链,并将待查询路径分解为若干条重链组成,在分解得到的每一条重链上进行区修区查,再合并所有结果,就能实现路径修改、路径查询。
时间复杂度分析
我们发现,从一个节点 \(u\) 转移到它的一个轻儿子 \(v\) 上, sz[v]
至少减小为 sz[u]
的 \(\frac{1}{2}\)。
因此任意一条自上而下的路径中所包含的重链条数一定不超 \(\log n\) 条(因为连接两条相邻重链的边一定是轻边)。
对每一条重链,线段树的区修区查复杂度的上界是 \(O(\log n)\)。因此单次修改的总时间复杂度上界为 \(O(\log^2 n)\)。
P3384 【模板】重链剖分/树链剖分
该题目中还用一个操作:子树修改子树查询。
我们注意到,树剖的本质仍然是一种 dfs
序,只不过进行了一些合法的调整。因此,子树内所有节点的 dfs
序仍然连续,因此也可以使用普通的 dfs
序线段树维护。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 |
|
250610 模拟赛 T2
请点击标题链接查看。
P4211 [LNOI2014] LCA
题意
给定一棵包含 \(n\) 个节点的树,有 \(m\) 次询问,每次询问给定 \((l,r,x)\),表示询问
先对查询进行差分,转换成前缀的查询,然后我们就可以对节点编号进行扫描线。
利用 \(dep\) 的性质,我们有简单的做法。考虑 \(y\) 对 \(x\) 的贡献,我们可以对 \(1\to y\) 的链加一,然后直接查询 \(1\to x\) 链的权值和,就是 \(dep\big[\operatorname{lca}(x,y)\big]\)。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
|
P3345 [ZJOI2015] 幻想乡战略游戏
题意
给定一棵 \(n\) 个节点的无根树,点有点权,边有边权。有 \(q\) 次修改,每次修改会修改一个节点的点权,然后立即询问树的加权重心以及加权深度和。
\(n,q\le 10^5\)
先考虑如何找到加权重心。重心的位置显然和边权无关。考虑重心的一个定义:
最深的满足 \(sz[x]\ge \lceil\frac{n}{2}\rceil\) 的节点。
容易发现,满足 \(sz[x]\ge \lceil\frac{n}{2}\rceil\) 的 \(x\) 分布在一条根链上,因此 dfn
序随深度增加而增加。使用树剖维护 sz
,线段树上二分即可。
然后考虑怎么求加权深度和。推一下式子:
其中 \(dis(1,x)\) 省略为 \(dis(x)\)。前两项都是平凡的。第三项利用上一题的技巧,我们给 \(x\) 的根链上的每个点 \(y\) 都加上 \(a_x\times w\big(fa[y], y\big)\),查询 \(rt\) 的根链权值和就是第三项的值。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
|