成都外国语学校信息学八月集训 Day1

Author：薇薇安
发布时间：August 19, 2019
217views
No comments
1882 words
Categories： OI

今天内容主要为树~~熟~~链~~练~~剖~~泼~~分~~粪~~。

## 目的

将一棵树划分成若干条链，用数据结构去维护每条链。

## 定义

- $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

如果您觉得我的文章有用，给颗糖糖吧~