Loj#139 树链剖分

题目链接

问题分析

一道比较标准的模板题。唯一需要考虑的是换根操作。

发现换根对链上的操作并没有影响，考虑对树上以\(u\)为根子树的影响。设原树上以\(u\)为根的子树是\(T\)。如果新的根在\(T\)的外部，那么以\(u\)为根的子树不变。如果新根就是\(u\)，那么子树就是整棵树。否则，取原树中\(u\)的一个儿子\(v\)，\(v\)包含新的根，那么新的以\(u\)为根的子树就是整棵树去掉原树中以\(v\)为根的子树。所以我们其实并不需要改变树的结构，只需要记录根节点位置就好。

参考程序

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int Maxn = 100010;
struct edge {
    int To, Next;
    edge() {}
    edge( int _To, int _Next ) : To( _To ), Next( _Next ) {}
};
edge Edge[ Maxn << 1 ];
int Start[ Maxn ], Used;
int A[ Maxn ], N, M, Root, Cnt;
int Size[ Maxn ], Son[ Maxn ], Father[ Maxn ], Deep[ Maxn ], Top[ Maxn ], Ind[ Maxn ], Ref[ Maxn ], Max[ Maxn ];
LL Sum[ Maxn << 2 ], Tag[ Maxn << 2 ];

inline void AddEdge( int x, int y ) {
    Edge[ ++Used ] = edge( y, Start[ x ] );
    Start[ x ] = Used;
    return;
}
void Dfs1( int Index, int Fa ) {
    Deep[ Index ] = Deep[ Fa ] + 1;
    Size[ Index ] = 1;
    Father[ Index ] = Fa;
    for( int T = Start[ Index ]; T; T = Edge[ T ].Next ) {
        Dfs1( Edge[ T ].To, Index );
        if( Size[ Edge[ T ].To ] > Size[ Son[ Index ] ] ) Son[ Index ] = Edge[ T ].To;
        Size[ Index ] += Size[ Edge[ T ].To ];
    }
    return;
}
void Dfs2( int Index ) {
    Ind[ Index ] = ++Cnt;
    Ref[ Cnt ] = Index;
    if( Son[ Index ] ) {
        Top[ Son[ Index ] ] = Top[ Index ];
        Dfs2( Son[ Index ] );
    }
    for( int T = Start[ Index ]; T; T = Edge[ T ].Next ) {
        if( Edge[ T ].To == Son[ Index ] ) continue;
        Top[ Edge[ T ].To ] = Edge[ T ].To;
        Dfs2( Edge[ T ].To );
    }
    Max[ Index ] = Cnt;
    return;
}
void Build( int Index, int Left, int Right ) {
    if( Left == Right ) {
        Sum[ Index ] = A[ Ref[ Left ] ];
        return;
    }
    int Mid = ( Left + Right ) >> 1;
    Build( Index << 1, Left, Mid );
    Build( Index << 1 | 1, Mid + 1, Right );
    Sum[ Index ] = Sum[ Index << 1 ] + Sum[ Index << 1 | 1 ];
    return;
}
void TagDown( int Index, int Left, int Right ) {
    if( Left == Right ) return;
    if( Tag[ Index ] == 0 ) return;
    int Mid = ( Left + Right ) >> 1;
    Tag[ Index << 1 ] += Tag[ Index ];
    Tag[ Index << 1 | 1 ] += Tag[ Index ];
    Sum[ Index << 1 ] += ( Mid - Left + 1 ) * Tag[ Index ];
    Sum[ Index << 1 | 1 ] += ( Right - Mid ) * Tag[ Index ];
    Tag[ Index ] = 0;
    return;
}
void Add( int Index, int Left, int Right, int L, int R, int K ) {
    if( L > R ) return;
    TagDown( Index, Left, Right );
    if( L <= Left && Right <= R ) {
        Sum[ Index ] += K * ( Right - Left + 1 );
        Tag[ Index ] += K;
        return;
    }
    int Mid = ( Left + Right ) >> 1;
    if( L <= Mid ) Add( Index << 1, Left, Mid, L, R, K );
    if( R > Mid ) Add( Index << 1 | 1, Mid + 1, Right, L, R, K );
    Sum[ Index ] = Sum[ Index << 1 ] + Sum[ Index << 1 | 1 ];
    return;
}
LL Query( int Index, int Left, int Right, int L, int R ) {
    if( L > R ) return 0;
    TagDown( Index, Left, Right );
    if( L <= Left && Right <= R ) return Sum[ Index ];
    LL Ans = 0; int Mid = ( Left + Right ) >> 1;
    if( L <= Mid ) Ans += Query( Index << 1, Left, Mid, L, R );
    if( R > Mid ) Ans += Query( Index << 1 | 1, Mid + 1, Right, L, R );
    return Ans;
}
void AddLink( int u, int v, int k ) {
    while( Top[ u ] != Top[ v ] ) {
        if( Deep[ Top[ u ] ] < Deep[ Top[ v ] ] ) swap( u, v );
        Add( 1, 1, N, Ind[ Top[ u ] ], Ind[ u ], k );
        u = Father[ Top[ u ] ];
    }
    if( Deep[ u ] > Deep[ v ] ) swap( u, v );
    Add( 1, 1, N, Ind[ u ], Ind[ v ], k );
    return;
}
int Get( int y, int x ) {
    int Last = 0;
    while( Top[ x ] != Top[ y ] ) {
        Last = Top[ x ];
        x = Father[ Top[ x ] ];
    }
    if( x == y ) return Last;
    return Son[ y ];
}
void AddSubTree( int u, int k ) {
    if( u == Root ) {
        Add( 1, 1, N, 1, N, k );
        return;
    }
    if( Ind[ Root ] < Ind[ u ] || Ind[ Root ] > Max[ u ] ) {
        Add( 1, 1, N, Ind[ u ], Max[ u ], k );
        return;
    }
    int T = Get( u, Root );
    Add( 1, 1, N, 1, Ind[ T ] - 1, k );
    Add( 1, 1, N, Max[ T ] + 1, N, k );
    return;
}
LL QueryLink( int u, int v ) {
    LL Ans = 0;
    while( Top[ u ] != Top[ v ] ) {
        if( Deep[ Top[ u ] ] < Deep[ Top[ v ] ] ) swap( u, v );
        Ans += Query( 1, 1, N, Ind[ Top[ u ] ], Ind[ u ] );
        u = Father[ Top[ u ] ];
    }
    if( Deep[ u ] > Deep[ v ] ) swap( u, v );
    Ans += Query( 1, 1, N, Ind[ u ], Ind[ v ] );
    return Ans;
}
LL QuerySubTree( int u ) {
    if( u == Root )
        return Query( 1, 1, N, 1, N );
    if( Ind[ Root ] < Ind[ u ] || Ind[ Root ] > Max[ u ] )
        return Query( 1, 1, N, Ind[ u ], Max[ u ] );
    int T = Get( u, Root );
    return Query( 1, 1, N, 1, Ind[ T ] - 1 ) + Query( 1, 1, N, Max[ T ] + 1, N );
}
int main() {
    scanf( "%d", &N );
    Root = 1;
    for( int i = 1; i <= N; ++i ) scanf( "%d", &A[ i ] ); 
    for( int i = 1; i < N; ++i ) {
        int x; scanf( "%d", &x );
        AddEdge( x, i + 1 );
    }
    Dfs1( Root, 0 );
    Top[ Root ] = Root;
    Dfs2( Root );
    Build( 1, 1, N );
    
    scanf( "%d", &M );
    for( int i = 1; i <= M; ++i ) {
        int Opt; scanf( "%d", &Opt );
        if( Opt == 1 ) scanf( "%d", &Root );
        if( Opt == 2 ) {
            int x, y, k; scanf( "%d%d%d", &x, &y, &k );
            AddLink( x, y, k );
        }
        if( Opt == 3 ) {
            int x, k; scanf( "%d%d", &x, &k );
            AddSubTree( x, k );
        }
        if( Opt == 4 ) {
            int u, v; scanf( "%d%d", &u, &v );
            printf( "%lld\n", QueryLink( u, v ) );
        }
        if( Opt == 5 ) {
            int u; scanf( "%d", &u );
            printf( "%lld\n", QuerySubTree( u ) );
        }
    }
    return 0;
}

Loj#139 树链剖分

原文：https://www.cnblogs.com/chy-2003/p/11315302.html