树链剖分(初学)

首先看一下树链剖分是什么东西：

当我们要同时解决以下两个问题时：

1.求树上两点简单路径上的最大最小值(和）

2.修改树上两点简单路径上的边权(点权)

如果只用单独考虑，那么第一个就是树上差分，第二个是倍增，可是如果同时要有两个操作，那么时间复杂度就会大幅度退化，所以现在要用一个新的方法：树链剖分

它将一棵树剖成了几条链来组成，且每个点最多只会存在一条链上，且只出现一次。那么怎么进行剖分呢？

首先定义一些东西：

重儿子：父亲结点的所有儿子结点中，子树拥有结点数最多的结点。

轻儿子：父亲结点除了重儿子以外的所有儿子。

重边：父亲结点与重儿子的连边。

轻边：父亲结点与轻儿子的连边。

重链：所有重边所组成的一条链。

就是这个样子，粗的边就是重边，不过链的长度可以为0，就是只有一个点

 在进行树链剖分时，我们将进行这些变量声明：
f[u]:保存点u的父亲结点
d[u]:保存点u的深度
size[u]:保存以u为根节点的子树的结点个数
son[u]:保存点u的重儿子
top[u]:保存点u所在重链的顶端结点
id[u]:保存点u进行重新编号后的新的编号

然后就可以开始搞了：

inline void dfs( int x , int f ){
    sz[x] = 1;
    fa[x] = f;
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( v == f ) continue;
        depth[v] = depth[x] + 1;//求深度
        dfs( v , x );
        sz[x] += sz[v];//确定son[x]，用sz[v]较大的v坐
        if( sz[son[x]] < sz[v] )
            son[x] = v;
    }
}
inline void dfs2( int x , int f ){
    top[x] = f;//这条链的最高点
    id[x] = ++cnt;//进行编号
    if( !son[x] )
        return ;
    dfs2( son[x] , f );//先找重边，再找轻边
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( id[v] ) continue;
        dfs2( v ,v );
    }
}

void get_ans( int x ){
    int fx = top[x] , y = 1 , fy = top[1];//x,y的简单路径上的查询，这里y=1
    int sum = 0;
    while( fx != fy ){
        if( depth[fx] >= depth[fy] ){
            ans = 0;
            query( 1 , id[fx] , id[x] );//注意谁的编号大
            sum += ans;
            insert_( 1 , id[fx] , id[x] , 2 );
            x = fa[fx];fx = top[x];
        }
        else{
            ans = 0;
            query( 1 , id[fy] , id[y] );
            sum += ans;
            insert_( 1 , id[fy] , id[y] , 2 );
            y = fa[fy];fy = top[y];
        }
    }//在最后一个链内，还需要判断它们内部的距离
    if( depth[x] <= depth[y] ){
        ans = 0;
         query( 1 , id[x] , id[y] );
        sum += ans;
        insert_( 1 , id[x] , id[y] , 2 );
    }
    else{
        ans = 0;
        query( 1 , id[y] , id[x] );
        sum += ans;
        insert_( 1 , id[y] , id[x] , 2 );
    }
    printf( "%d\n" , sum );
}

先来一个板题:软件包管理器

我们要知道一个性质，对于一个点x，它的子树编号一定是比他大的，这样对于子树查找与修改就很简单了

然后区间修改就用线段树即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN = 100013;
int n;
struct node{
    int l , r;
    int lazy , sum;
}tre[MAXN*4];
int sz[MAXN] , son[MAXN] , top[MAXN] , depth[MAXN] , id[MAXN] , fa[MAXN] , cnt;
vector<int> G[MAXN];
inline void dfs( int x , int f ){
    sz[x] = 1;
    fa[x] = f;
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( v == f ) continue;
        depth[v] = depth[x] + 1;
        dfs( v , x );
        sz[x] += sz[v];
        if( sz[son[x]] < sz[v] )
            son[x] = v;
    }
}
inline void dfs2( int x , int f ){
    top[x] = f;
    id[x] = ++cnt;
    if( !son[x] )
        return ;
    dfs2( son[x] , f );
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( id[v] ) continue;
        dfs2( v ,v );
    }
}
inline void build( int i , int l , int r ){
    tre[i].l = l , tre[i].r = r;
    tre[i].sum = tre[i].r - tre[i].l + 1;
    tre[i].lazy = 0;
    int mid = ( l + r ) / 2;
    if( l == r ) return ;
    build( i * 2 , l , mid );
    build( i * 2 + 1 , mid + 1 , r ) ;
}
inline void pushdown( int i ){
    if( tre[i].lazy ){
        if( tre[i].lazy == 1 ){
            tre[i*2].lazy = tre[i*2+1].lazy = 1;
            tre[i].sum = tre[i].r - tre[i].l + 1;
            tre[i*2].sum = tre[i*2].r - tre[i*2].l + 1;
            tre[i*2+1].sum = tre[i*2+1].r - tre[i*2+1].l + 1;
        }
        else{
            tre[i*2].lazy = tre[i*2+1].lazy = 2;
            tre[i].sum = 0;
            tre[i*2].sum = 0;
            tre[i*2+1].sum = 0;
        }
        tre[i].lazy = 0;
    }
}
int ans;
inline void query( int i , int l , int r ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        ans += tre[i].sum;
        return ;
    }
    pushdown( i );
    query( i * 2 , l , r );
    query( i * 2 + 1 , l , r );
    tre[i].sum = tre[i*2].sum + tre[i*2+1].sum;
}
inline void insert_( int i , int l , int r , int delta ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        tre[i].lazy = delta;
        if( delta == 1 )
            tre[i].sum = tre[i].r - tre[i].l + 1;
        else
            tre[i].sum = 0;
        return ;
    }
    pushdown( i );
    insert_( i * 2 , l , r , delta );
    insert_( i * 2 + 1 , l , r , delta );
    tre[i].sum = tre[i*2].sum + tre[i*2+1].sum;
}
void get_ans( int x ){
    int fx = top[x] , y = 1 , fy = top[1];
    int sum = 0;
    while( fx != fy ){
        if( depth[fx] >= depth[fy] ){
            ans = 0;
            query( 1 , id[fx] , id[x] );
            sum += ans;
            insert_( 1 , id[fx] , id[x] , 2 );
            x = fa[fx];fx = top[x];
        }
        else{
            ans = 0;
            query( 1 , id[fy] , id[y] );
            sum += ans;
            insert_( 1 , id[fy] , id[y] , 2 );
            y = fa[fy];fy = top[y];
        }
    }
    if( depth[x] <= depth[y] ){
        ans = 0;
         query( 1 , id[x] , id[y] );
        sum += ans;
        insert_( 1 , id[x] , id[y] , 2 );
    }
    else{
        ans = 0;
        query( 1 , id[y] , id[x] );
        sum += ans;
        insert_( 1 , id[y] , id[x] , 2 );
    }
    printf( "%d\n" , sum );
}
void get_( int x ){
    ans = 0; query( 1 , id[x] , id[x] + sz[x] - 1 );
    printf( "%d\n" , sz[x] - ans );
    insert_( 1 , id[x] , id[x] + sz[x] - 1 , 1 );
}
int main(){
    scanf( "%d" , &n );
    build( 1 , 1 , n );
    for( register int i = 1 ; i < n ; i ++ ){
        int x;
        scanf( "%d" ,&x );
        x ++;
        G[x].push_back( i + 1 );G[i+1].push_back( x );
    }
    depth[1] = 1;
    dfs( 1 , 1 );
    top[1] = 1;
    dfs2( 1 , 1 );
    int q;
    scanf( "%d" , &q );
    while( q -- ){
        char s[20];
        int x;scanf( "%s" , s );
        scanf( "%d" , &x );
        x ++;
        if( s[0] == 'i' ){
            get_ans( x );
        }
        else{
            get_( x );
        }
    }
    return 0;
}

 

然而还有一道题：Tree

稍微难一点，但是还好，主要是自己的lazy标记打错了，调了半天.... 注意懒标记用^=1变两次相当于没变

然后我是将边权移到节点上，统一将边权向下移动到儿子点，对于1特判一下即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN = 10003;
int n;
struct node{
    int l , r;
    int lazy , sum , sum2;
}tre[MAXN*4];
int f[MAXN][23];
int X[MAXN] , Y[MAXN] , now[MAXN] , belong[MAXN];
int sz[MAXN] , son[MAXN] , top[MAXN] , depth[MAXN] , id[MAXN] , fa[MAXN] , cnt , E[MAXN];
vector<int> G[MAXN];
inline void dfs( int x , int fp ){
    sz[x] = 1;
    fa[x] = fp;
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( v == fp ) continue;
        depth[v] = depth[x] + 1;
        dfs( v , x );
        f[v][0] = x;
        sz[x] += sz[v];
        if( sz[son[x]] < sz[v] )
            son[x] = v;
    }
}
inline void dfs2( int x , int f ){
    top[x] = f;
    id[x] = ++cnt;
    if( !son[x] )
        return ;
    dfs2( son[x] , f );
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( id[v] ) continue;
        dfs2( v ,v );
    }
}
void jump( int &x , int mu ){
    for( int i = 20 ; i >= 0 ; i -- ){
        if( depth[f[x][i]] >= mu )
            x = f[x][i];
    }
}
int LCA( int x , int y ){
    if( depth[x] > depth[y] )
        jump( x , depth[y] );
    else if( depth[y] > depth[x] )
        jump( y , depth[x] );
    if( x == y ) return x;
    for( int i = 20 ; i >= 0 ; i -- )
        if( f[x][i] != f[y][i] )
            x = f[x][i] , y = f[y][i];
    return f[x][0];
}
inline void build( int i , int l , int r ){
    tre[i].l = l , tre[i].r = r;
    tre[i].lazy = 0;
    int mid = ( l + r ) / 2;
    if( l == r ){
        if( l == 1 ){
            tre[i].sum = -0x7f7f7f7f;
            tre[i].sum2 = 0x7f7f7f7f;
            return ;
        }
        tre[i].sum = tre[i].sum2 = now[r];
        return ;
    }
    build( i * 2 , l , mid );
    build( i * 2 + 1 , mid + 1 , r ) ;
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
inline void pushdown( int i ){
    if( tre[i].lazy != 0 ){
        tre[i*2].lazy ^= 1;tre[i*2+1].lazy ^= 1;
        swap( tre[i*2].sum , tre[i*2].sum2 );
        swap( tre[i*2+1].sum , tre[i*2+1].sum2 );
        tre[i*2].sum *= -1;tre[i*2].sum2 *= -1;
        tre[i*2+1].sum *= -1;tre[i*2+1].sum2 *= -1;
        tre[i].lazy = 0;
    }
}
int ans;
inline void query( int i , int l , int r ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        ans = max( ans , tre[i].sum );
        return ;
    }
    pushdown( i );
    query( i * 2 , l , r );
    query( i * 2 + 1 , l , r );
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
inline void insert_( int i , int l , int r ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        tre[i].lazy ^= 1;
        tre[i].sum *= -1;
        tre[i].sum2 *= -1;
        swap( tre[i].sum , tre[i].sum2 );
        return ;
    }
    pushdown( i );
    insert_( i * 2 , l , r );
    insert_( i * 2 + 1 , l , r );
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
int get_ans( int x , int y ){
    int fx = top[x] , fy = top[y];
    int sum = -0x7f7f7f7f;
    while( fx != fy ){
        if( depth[fx] >= depth[fy] ){
            ans = -0x7f7f7f7f;
            query( 1 , id[fx] , id[x] );
            sum = max( sum , ans );
            x = fa[fx];fx = top[x];
        }
        else{
            ans = -0x7f7f7f7f;
            query( 1 , id[fy] , id[y] );
            sum = max( sum , ans );
            y = fa[fy];fy = top[y];
        }
    }
    if( x == y )
        return sum;
    if( depth[y] <= depth[x] )
        swap( x , y );
    ans = -0x7f7f7f7f;
    query( 1 , id[son[x]] , id[y] );
    sum = max( sum , ans );
    return sum;
}
void get_change( int x , int y ){
    int fx = top[x] , fy = top[y];
    while( fx != fy ){
        if( depth[fx] >= depth[fy] ){
            insert_( 1 , id[fx] , id[x] );
            x = fa[fx];fx = top[x];
        }
        else{
            insert_( 1 , id[fy] , id[y] );
            y = fa[fy];fy = top[y];
        }
    }
    if( x == y )
        return ;
    if( depth[y] <= depth[x] )
        swap( x , y );
    insert_( 1 , id[son[x]] , id[y] );
}
inline void insert_1( int i , int l , int r , int delta ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        tre[i].sum = tre[i].sum2 = delta;
        return ;
    }
    pushdown( i );
    insert_1( i * 2 , l , r , delta );
    insert_1( i * 2 + 1 , l , r , delta );
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
int main(){
    scanf( "%d" , &n );
    for( register int i = 1 ; i < n ; i ++ ){
        int x , y , z;
        scanf( "%d%d%d" ,&x , &y , &z );
        X[i] = x , Y[i] = y;
        G[x].push_back( y );
        G[y].push_back( x );
        E[i] = z;
    }
    depth[1] = 1;
    dfs( 1 , 1 );
    for( int j = 1 ; j <= 20 ; j ++ )
        for( int i = 1 ; i <= n ; i ++ )
            f[i][j] = f[f[i][j-1]][j-1];
    top[1] = 1;
    dfs2( 1 , 1 );
    for( int i = 1 ; i < n ; i ++ ){
        int x = X[i] , y = Y[i];
        if( depth[x] > depth[y] ){
            now[id[x]] = E[i];
            belong[i] = id[x];
        }
        else
            now[id[y]] = E[i] , belong[i] = id[y];
    }
    build( 1 , 1 , n );
    char s[20];
    int x , y;#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN = 10003;
int n;
struct node{
    int l , r;
    int lazy , sum , sum2;
}tre[MAXN*4];
int f[MAXN][23];
int X[MAXN] , Y[MAXN] , now[MAXN] , belong[MAXN];
int sz[MAXN] , son[MAXN] , top[MAXN] , depth[MAXN] , id[MAXN] , fa[MAXN] , cnt , E[MAXN];
vector<int> G[MAXN];
inline void dfs( int x , int fp ){
    sz[x] = 1;
    fa[x] = fp;
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( v == fp ) continue;
        depth[v] = depth[x] + 1;
        dfs( v , x );
        f[v][0] = x;
        sz[x] += sz[v];
        if( sz[son[x]] < sz[v] )
            son[x] = v;
    }
}
inline void dfs2( int x , int f ){
    top[x] = f;
    id[x] = ++cnt;
    if( !son[x] )
        return ;
    dfs2( son[x] , f );
    for( register int i = 0 ; i < G[x].size() ; i ++ ){
        int v = G[x][i];
        if( id[v] ) continue;
        dfs2( v ,v );
    }
}
void jump( int &x , int mu ){
    for( int i = 20 ; i >= 0 ; i -- ){
        if( depth[f[x][i]] >= mu )
            x = f[x][i];
    }
}
int LCA( int x , int y ){
    if( depth[x] > depth[y] )
        jump( x , depth[y] );
    else if( depth[y] > depth[x] )
        jump( y , depth[x] );
    if( x == y ) return x;
    for( int i = 20 ; i >= 0 ; i -- )
        if( f[x][i] != f[y][i] )
            x = f[x][i] , y = f[y][i];
    return f[x][0];
}
inline void build( int i , int l , int r ){
    tre[i].l = l , tre[i].r = r;
    tre[i].lazy = 0;
    int mid = ( l + r ) / 2;
    if( l == r ){
        if( l == 1 ){
            tre[i].sum = -0x7f7f7f7f;
            tre[i].sum2 = 0x7f7f7f7f;
            return ;
        }
        tre[i].sum = tre[i].sum2 = now[r];
        return ;
    }
    build( i * 2 , l , mid );
    build( i * 2 + 1 , mid + 1 , r ) ;
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
inline void pushdown( int i ){
    if( tre[i].lazy != 0 ){
        tre[i*2].lazy ^= 1;tre[i*2+1].lazy ^= 1;
        swap( tre[i*2].sum , tre[i*2].sum2 );
        swap( tre[i*2+1].sum , tre[i*2+1].sum2 );
        tre[i*2].sum *= -1;tre[i*2].sum2 *= -1;
        tre[i*2+1].sum *= -1;tre[i*2+1].sum2 *= -1;
        tre[i].lazy = 0;
    }
}
int ans;
inline void query( int i , int l , int r ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        ans = max( ans , tre[i].sum );
        return ;
    }
    pushdown( i );
    query( i * 2 , l , r );
    query( i * 2 + 1 , l , r );
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
inline void insert_( int i , int l , int r ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        tre[i].lazy ^= 1;
        tre[i].sum *= -1;
        tre[i].sum2 *= -1;
        swap( tre[i].sum , tre[i].sum2 );
        return ;
    }
    pushdown( i );
    insert_( i * 2 , l , r );
    insert_( i * 2 + 1 , l , r );
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
int get_ans( int x , int y ){
    int fx = top[x] , fy = top[y];
    int sum = -0x7f7f7f7f;
    while( fx != fy ){
        if( depth[fx] >= depth[fy] ){
            ans = -0x7f7f7f7f;
            query( 1 , id[fx] , id[x] );
            sum = max( sum , ans );
            x = fa[fx];fx = top[x];
        }
        else{
            ans = -0x7f7f7f7f;
            query( 1 , id[fy] , id[y] );
            sum = max( sum , ans );
            y = fa[fy];fy = top[y];
        }
    }
    if( x == y )
        return sum;
    if( depth[y] <= depth[x] )
        swap( x , y );
    ans = -0x7f7f7f7f;
    query( 1 , id[son[x]] , id[y] );
    sum = max( sum , ans );
    return sum;
}
void get_change( int x , int y ){
    int fx = top[x] , fy = top[y];
    while( fx != fy ){
        if( depth[fx] >= depth[fy] ){
            insert_( 1 , id[fx] , id[x] );
            x = fa[fx];fx = top[x];
        }
        else{
            insert_( 1 , id[fy] , id[y] );
            y = fa[fy];fy = top[y];
        }
    }
    if( x == y )
        return ;
    if( depth[y] <= depth[x] )
        swap( x , y );
    insert_( 1 , id[son[x]] , id[y] );
}
inline void insert_1( int i , int l , int r , int delta ){
    if( tre[i].r < l || tre[i].l > r ) return ;
    if( l <= tre[i].l && tre[i].r <= r ){
        tre[i].sum = tre[i].sum2 = delta;
        return ;
    }
    pushdown( i );
    insert_1( i * 2 , l , r , delta );
    insert_1( i * 2 + 1 , l , r , delta );
    tre[i].sum = max( tre[i*2].sum , tre[i*2+1].sum );
    tre[i].sum2 = min( tre[i*2].sum2 , tre[i*2+1].sum2 );
}
int main(){
    scanf( "%d" , &n );
    for( register int i = 1 ; i < n ; i ++ ){
        int x , y , z;
        scanf( "%d%d%d" ,&x , &y , &z );
        X[i] = x , Y[i] = y;
        G[x].push_back( y );
        G[y].push_back( x );
        E[i] = z;
    }
    depth[1] = 1;
    dfs( 1 , 1 );
    for( int j = 1 ; j <= 20 ; j ++ )
        for( int i = 1 ; i <= n ; i ++ )
            f[i][j] = f[f[i][j-1]][j-1];
    top[1] = 1;
    dfs2( 1 , 1 );
    for( int i = 1 ; i < n ; i ++ ){
        int x = X[i] , y = Y[i];
        if( depth[x] > depth[y] ){
            now[id[x]] = E[i];
            belong[i] = id[x];
        }
        else
            now[id[y]] = E[i] , belong[i] = id[y];
    }
    build( 1 , 1 , n );
    char s[20];
    int x , y;
    while( 1 ){
        scanf( "%s" , s );
        if( s[0] == 'D' )
            return 0;
        int x , y;
        scanf( "%d%d" , &x , &y );
        if( s[0] == 'Q' ){
            printf( "%d\n" , get_ans( x , y ) );
        }
        else if( s[0] == 'C' ){
            insert_1( 1 , belong[x] , belong[x] , y );
        }
        else{
            get_change( x , y );
        }
    }
    return 0;
}

    while( 1 ){
        scanf( "%s" , s );
        if( s[0] == 'D' )
            return 0;
        int x , y;
        scanf( "%d%d" , &x , &y );
        if( s[0] == 'Q' ){
            printf( "%d\n" , get_ans( x , y ) );
        }
        else if( s[0] == 'C' ){
            insert_1( 1 , belong[x] , belong[x] , y );
        }
        else{
            get_change( x , y );
        }
    }
    return 0;
}