Loading... 今天内容主要为树~~熟~~链~~练~~剖~~泼~~分~~粪~~。 <div class='handsome_aplayer' data-preload="auto" data-autoplay="false" data-listMaxHeight="340px" data-order="list" data-media="netease" data-id="1309394162" data-type="song" data-size="large" data-auto="false"> <div class="handsome_aplayer_music" data-id="1309394162" data-server="netease" data-type="song" data-auth="auth"></div> </div> ## 目的 将一棵树划分成若干条链,用数据结构去维护每条链。 ## 定义 - $size(x)$为以$x$为根的子树的节点个数。 - 令$v$为$u$的儿子节点中$size$值最大的节点,那么边$(u,v)$被称为重边,树中重边之外的边被称为轻边。 - 全部由重边组成的路径是重路径(也叫重链)。 - `siz`数组,用来保存以x为根的子树节点个数。 - `top`数组,用来保存当前节点的所在链的顶端节点。 - `son`数组,用来保存重儿子。 - `dep`数组,用来保存当前节点的深度。 - `fa`数组,用来保存当前节点的父亲。 - `tid`数组,用来保存树中每个节点剖分后的新编号。 - `rank`数组,用来保存当前节点在线段树中的位置。 ## 性质 - 对于轻边$(u,v)$,$size(v) \leq \frac{size(u)}{2}$。 - 从根到某一点的路径上,不超过$log_2n$条轻边,不超过$log_2n$条重路径。 ## 方法 ### 第一次深度优先搜索 目的为找重边。 用一次`DFS`或`BFS`求出每个节点的`siz`(即自己和自己的子孙节点个数),然后每一个节点选择一个尺寸最大的子节点(有多个最大择随便选择一个),连接该节点与这个子节点的边化为重边。 ### 第二次深度优先搜索 目的为连重边成重链。 以根节点为起点,沿重边向下拓展,拉成重链。不在当前重链上的节点,都以该节点为起点向下重新拉一条重链。于是每一个节点都属于且仅属于一条重链。 ### 操作 剖分完之后,每条重链就相当于一段区间,用数据结构去维护。把所有的重链首尾相接,放到同一个数据结构上,然后维护这一个整体即可。 ### 修改 #### 单点修改 直接数据结构操作。 #### 整体修改点和点的路径上的权值 ##### 在同一条重链上 直接数据结构修改`tid[u]`至`tid[v]`间的值。 ##### 不在同一条重链上 一边进行修改,一边将两个点同一条重链上靠,先求得两点的最近公共祖先,操作就变为整体修改两点分别到最近公共祖先。然后就变成了前一种情况。 或每次在点`u`和点`v`中,选择`dep[top[x]]`较大的点`x`,修改`x`与`top[x]`间的各权值,再跳至`fa[top[x]]`,直到点`u`和点`v`在同一条重链上。 ## 特点 树链剖分的独特之处是可以对路径进行修改,一般结合线段树进行处理,查询更新的复杂度就是$O(log_2n)$,这是LCA在线倍增所不能做到的。 ## 代码 ```cpp #include <cstring> #include <iostream> #include <stdio.h> using namespace std; #define MAXN 30010 struct edge { int to, nxt; } e[MAXN << 1]; int head[MAXN], ei = 0; inline void add( int x, int y ) { ei++; e[ei].to = y; e[ei].nxt = head[x]; head[x] = ei; } int n, q; int fa[MAXN], siz[MAXN], son[MAXN], dep[MAXN], top[MAXN], in[MAXN], out[MAXN], id[MAXN], dfsi = 0; void dfs1( int f, int x ) { fa[x] = f; dep[x] = dep[fa[x]] + 1; siz[x] = 1; son[x] = 0; int maxn = -1; for ( int i = head[x]; i != 0; i = e[i].nxt ) { int y = e[i].to; if ( y == f ) { continue; } dfs1( x, y ); siz[x] += siz[y]; if ( maxn < siz[y] ) { maxn = siz[y]; son[x] = y; } } } void dfs2( int tp, int x ) { dfsi++; in[x] = dfsi; id[dfsi] = x; top[x] = tp; if ( son[x] == 0 ) { return; } dfs2( tp, son[x] ); for ( int i = head[x]; i != 0; i = e[i].nxt ) { int y = e[i].to; if ( y == son[x] || y == fa[x] ) { continue; } dfs2( y, y ); } out[x] = dfsi; } int ma[MAXN << 2], sum[MAXN << 2]; int a[MAXN]; inline void pushup( int o ) { ma[o] = max( ma[o * 2], ma[o * 2 + 1] ); sum[o] = sum[o * 2] + sum[o * 2 + 1]; } void build( int o, int lf, int rg ) { if ( lf == rg ) { ma[o] = a[id[lf]]; sum[o] = a[id[lf]]; return; } int mid = ( lf + rg ) >> 1; build( o * 2, lf, mid ); build( o * 2 + 1, mid + 1, rg ); pushup( o ); } void modify( int o, int lf, int rg, int x, int k ) { if ( lf == x && rg == x ) { ma[o] = k; sum[o] = k; return; } int mid = ( lf + rg ) >> 1; if ( x <= mid ) { modify( o * 2, lf, mid, x, k ); } else { modify( o * 2 + 1, mid + 1, rg, x, k ); } pushup( o ); } int m_query( int o, int lf, int rg, int L, int R ) { if ( L <= lf && rg <= R ) { return ma[o]; } int mid = ( lf + rg ) >> 1; int ans = 0x80808080; if ( L <= mid ) { ans = max( ans, m_query( o * 2, lf, mid, L, R ) ); } if ( mid < R ) { ans = max( ans, m_query( o * 2 + 1, mid + 1, rg, L, R ) ); } pushup( o ); return ans; } int s_query( int o, int lf, int rg, int L, int R ) { if ( L <= lf && rg <= R ) { return sum[o]; } int mid = ( lf + rg ) >> 1; int ans = 0; if ( L <= mid ) { ans += s_query( o * 2, lf, mid, L, R ); } if ( mid < R ) { ans += s_query( o * 2 + 1, mid + 1, rg, L, R ); } pushup( o ); return ans; } int qmax( int x, int y ) { int ans = 0x80808080; while ( top[x] != top[y] ) { if ( dep[top[x]] < dep[top[y]] ) { swap( x, y ); } ans = max( ans, m_query( 1, 1, n, in[top[x]], in[x] ) ); x = fa[top[x]]; } if ( dep[x] > dep[y] ) { swap( x, y ); } return max( ans, m_query( 1, 1, n, in[x], in[y] ) ); } int smax( int x, int y ) { int ans = 0; while ( top[x] != top[y] ) { if ( dep[top[x]] < dep[top[y]] ) { swap( x, y ); } ans += s_query( 1, 1, n, in[top[x]], in[x] ); x = fa[top[x]]; } if ( dep[x] > dep[y] ) { swap( x, y ); } return ans + s_query( 1, 1, n, in[x], in[y] ); } int main() { ios::sync_with_stdio( false ); cin >> n; for ( int i = 1; i < n; i++ ) { int x, y; cin >> x >> y; add( x, y ); add( y, x ); } for ( int i = 1; i <= n; i++ ) { cin >> a[i]; } dfs1( 1, 1 ); dfs2( 1, 1 ); build( 1, 1, n ); cin >> q; for ( int i = 1; i <= q; i++ ) { string ch; cin >> ch; int x, y; cin >> x >> y; if ( ch[0] == 'C' ) { modify( 1, 1, n, in[x], y ); } else if ( ch[1] == 'S' ) { cout << smax( x, y ) << endl; } else { cout << qmax( x, y ) << endl; } } } ```<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/444.html">https://www.starroad.top/archives/444.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:August 21st, 2019 at 09:15 pm © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat