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

目的

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

定义

• $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在线倍增所不能做到的。

代码

#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;
        }
    }
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/444.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。