洛谷 P3979 遥远的国度-526互联

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

#define lid id << 1 
#define rid id << 1 | 1

using namespace std;

int n, m, w[5211314], root, rank_[5211314], new_id;
int head[5211314], next_[5211314], to[5211314], cnt;
int now_root;

struct Segment_Tree {
	int l, r, lazy, min;
}s_tree[5211314];

struct Heavy_Light_Tree {
	int Top;
	int Father;
	int Id;
	int Childtree_max_id;
	int Heavy_Son;
	int Size;
	int Deep;
}h_tree[5211314];

int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while ( ch < '0' || ch > '9' ) {
		if ( ch == '-' ) {
			f *= -1;
		}
		ch = getchar();
	}
	while ( ch >= '0' && ch <= '9' ) {
		x = ( x << 1 ) + ( x << 3 ) + ( ch -'0' );
		ch = getchar();
	}
	return x * f;
} 

void print_( int x ) {
	if ( x < 0 ) putchar('-'), x *= -1;
	if ( x > 9 ) print_( x / 10 );
	putchar( x % 10 + '0' );
	return;
}

void print( int x ) {
	print_( x );
	putchar('\n');
}

inline void add_poi( int v1 , int v2 ) {
	++ cnt;
	next_[cnt] = head[v1];
	head[v1] = cnt;
	to[cnt] = v2;
	return;
}

inline void pushdown( int id ) {
	if ( s_tree[id].lazy ) {
		s_tree[lid].lazy = s_tree[id].lazy;
		s_tree[rid].lazy = s_tree[id].lazy;
		s_tree[lid].min = s_tree[id].lazy;
		s_tree[rid].min = s_tree[id].lazy;
		s_tree[id].lazy = 0;
	}
	return;
}

void DFS_SON( int now , int fa ) {
	h_tree[now].Father = fa;
	h_tree[now].Size = 1;
	h_tree[now].Deep = h_tree[fa].Deep + 1;
	for (int i = head[now]; i != 0; i = next_[i]) {
		if ( to[i] != fa ) {
			DFS_SON( to[i] , now );
			h_tree[now].Size += h_tree[to[i]].Size;
			if ( h_tree[h_tree[now].Heavy_Son].Size < h_tree[to[i]].Size ) {
				h_tree[now].Heavy_Son = to[i];
			}
		}
	}
	return;
}

void DFS_LINE( int now , int top ) {
	h_tree[now].Top = top;
	h_tree[now].Id = ++ new_id;
	h_tree[now].Childtree_max_id = new_id;
	rank_[new_id] = now;
	if ( h_tree[now].Heavy_Son ) {
		DFS_LINE( h_tree[now].Heavy_Son , top );
        h_tree[now].Childtree_max_id = max( h_tree[now].Childtree_max_id , h_tree[h_tree[now].Heavy_Son].Childtree_max_id );
	}
	for (int i = head[now]; i != 0; i = next_[i]) {
		if ( h_tree[now].Heavy_Son != to[i] && h_tree[now].Father != to[i] ) {
			DFS_LINE( to[i] , to[i] );
			h_tree[now].Childtree_max_id = max( h_tree[now].Childtree_max_id , h_tree[to[i]].Childtree_max_id );
		}
	}
	return;
}

void build_tree( int id , int l , int r ) {
	s_tree[id].l = l;
	s_tree[id].r = r;
	if ( l == r ) {
		s_tree[id].min = w[rank_[l]];
		return;
	}
	int mid = ( l + r ) >> 1;
	build_tree( lid , l , mid );
	build_tree( rid , mid + 1 , r );
	s_tree[id].min = min( s_tree[lid].min , s_tree[rid].min );
	return;
}

void s_update( int id , int l , int r , int add_num ) {
	if ( s_tree[id].l >= l && s_tree[id].r <= r ) {
		s_tree[id].min = add_num;
		s_tree[id].lazy = add_num;
		return;
	}
	pushdown( id );
	int mid = ( s_tree[id].l + s_tree[id].r ) >> 1;
	if ( l <= mid ) s_update( lid , l , r , add_num );
	if ( r > mid ) s_update( rid , l , r , add_num );
	s_tree[id].min = min( s_tree[lid].min , s_tree[rid].min );
	//可能存在id的儿子的儿子被修改了，所以要更新一下 
	return;
}

void h_update( int x , int y , int update_num ) {
	int left, right;
	while ( h_tree[x].Top != h_tree[y].Top ) {
		if ( h_tree[h_tree[x].Top].Deep < h_tree[h_tree[y].Top].Deep ) {
			swap( x , y );
		}
		left = h_tree[h_tree[x].Top].Id;
		right = h_tree[x].Id;
		s_update( 1 , left , right , update_num );
		x = h_tree[h_tree[x].Top].Father;
	}
	if ( h_tree[x].Deep > h_tree[y].Deep ) {
		swap( x , y );
	}
	left = h_tree[x].Id;
	right = h_tree[y].Id;
	s_update( 1 , left , right , update_num );
	return;
}

int s_query( int id , int l , int r ) {
	int ans = 521131400 * 3;
  	if ( s_tree[id].l >= l && s_tree[id].r <= r ) {
		return s_tree[id].min;
	}
	pushdown( id );
	int mid = ( s_tree[id].l + s_tree[id].r ) >> 1;
	if ( l <= mid ) ans = min( ans , s_query( lid , l , r ) );
	if ( r > mid ) ans = min( ans , s_query( rid , l , r ) );
	return ans;
}

int main()
{
	n = read();
	m = read();
	for (int i = 1, u, v; i <= n - 1; ++ i) {
		u = read();
		v = read();
		add_poi( u , v );
		add_poi( v , u );
	}
	for (int i = 1; i <= n; ++ i) {
		w[i] = read();
	}
	for (int i = 1; i <= n * 4; ++ i) {
		s_tree[i].min = 521131400 * 3;
	}
	root = read();
	now_root = root;
	DFS_SON( root , root );
	DFS_LINE( root , root );
	build_tree( 1 , 1 , n );
	for (int i = 1, opt, x, y, v; i <= m; ++ i) {
		opt = read();
		if ( opt == 1 ) {
			x = read();
			now_root = x;
		}
		else if ( opt == 2 ) {
			x = read();
			y = read();
			v = read();
			h_update( x , y , v );
		}
		else if ( opt == 3 ) {
			//******核心思想******
			//查询方法:如果 查询点 有一个儿子的子树的最大和最小的id 包含 现在根节点 子树的最大最小id
			//         则这个儿子节点的子树包含 现在根节点的子树 
			//1.如果查询的点 是现在根节点的子树 则直接查询 查询点子树的最小值
			//2.如果查询的点的子树 不包含现在根节点 则也直接查询 查询点子树的最小值 
			//2.否则遍历一遍查询点的每个儿子
			//  比较 查询点的每个儿子的子树的最大最小id 与现在根节点的子树所包含的最大最小id
			//  查询点有一个儿子的子树 包含 根节点的子树 则查询 除了这个儿子的子树 之外的所有节点的最小值 
			x = read();
			if ( x == now_root ) {
				print( s_query( 1 , 1 , n ) );
			}
			else if ( h_tree[x].Id >= h_tree[now_root].Id && h_tree[x].Childtree_max_id <= h_tree[now_root].Childtree_max_id ) {
				//如果查询的点是现在根节点的子树
				print( s_query( 1 , h_tree[x].Id , h_tree[x].Childtree_max_id ) );
			} 
			else if ( h_tree[x].Id <= h_tree[now_root].Id && h_tree[x].Childtree_max_id >= h_tree[now_root].Childtree_max_id ) {
				//查询点有一个儿子的子树 包含 根节点的子树 则查询 除了这个儿子的子树 之外的所有节点的最小值 
				int l_rank, r_rank, minn;
				for (int i = head[x]; i != 0; i = next_[i]) {
					if ( h_tree[to[i]].Id <= h_tree[now_root].Id && h_tree[to[i]].Childtree_max_id >= h_tree[now_root].Childtree_max_id && to[i] != h_tree[x].Father ) {
						//注意判断这里的to[i]不等于now 
						l_rank = h_tree[to[i]].Id;
						r_rank = h_tree[to[i]].Childtree_max_id;
						break;
					}
				}
				minn = min( s_query( 1 , 1 , l_rank - 1 ) , s_query( 1 , r_rank + 1 , n ) );
				print( minn );
			}
			else {
				//如果查询的点的子树 不包含现在根节点
				print( s_query( 1 , h_tree[x].Id , h_tree[x].Childtree_max_id ) );
			}
		}
	}
	return 0;
}