题目链接
问题分析
一道比较标准的模板题。唯一需要考虑的是换根操作。
发现换根对链上的操作并没有影响，考虑对树上以\(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;
}
