记录编号	317876	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	遥远的国度	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	2.233 s
提交时间	2016-10-08 17:09:25	内存使用	8.69 MiB

#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;

const int maxnumber = 100100;
int n, m, num;
struct Edge
{
	int to, next;
}edges[maxnumber << 1];
int head[maxnumber], tot;
int value[maxnumber];
int depth[maxnumber], size[maxnumber], fa[maxnumber], son[maxnumber];
int top[maxnumber], dfn[maxnumber], id[maxnumber], end[maxnumber], dfsclock;
// end[i]: 点i子树的终止位置(dfn序)
int minn[maxnumber << 2], lazy[maxnumber << 2];
int capital;

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline void AddEdge(const int& from, const int& to)
{
	edges[++tot].to = to;
	edges[tot].next = head[from];
	head[from] = tot;
}

void Segment_Tree_Build(const int& l, const int& r, const int& rt)
{
	if(l == r){
		minn[rt] = value[id[l]];
		return;
	}
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	Segment_Tree_Build(l, mid, lch); 
	Segment_Tree_Build(mid+1, r, rch);
	minn[rt] = min(minn[lch], minn[rch]);
}

inline void PushDown(const int& rt)
{
	const int lch = rt << 1, rch = lch | 1;
	minn[lch] = lazy[rt]; minn[rch] = lazy[rt];
	lazy[lch] = lazy[rt]; lazy[rch] = lazy[rt];
	lazy[rt] = 0;
}

void Segment_Tree_Change(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
	if(l >= s && r <= t){
		minn[rt] = num;
		lazy[rt] = num;
		return;
	}
	if(lazy[rt]) PushDown(rt);// ************************************************************************
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	if(t <= mid) Segment_Tree_Change(l, mid, lch, s, t);
	else if(s >= mid + 1) Segment_Tree_Change(mid+1, r, rch, s, t);
	else{
		Segment_Tree_Change(l, mid, lch, s, mid);
		Segment_Tree_Change(mid+1, r, rch, mid+1, t);
	}
	minn[rt] = min(minn[lch], minn[rch]);
}

int Segment_Tree_Min(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
	if(l >= s && r <= t) return minn[rt];
	if(lazy[rt]) PushDown(rt);
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	if(t <= mid) return Segment_Tree_Min(l, mid, lch, s, t);
	else if(s >= mid + 1) return Segment_Tree_Min(mid+1, r, rch, s, t);
	return min(Segment_Tree_Min(l, mid, lch, s, mid), Segment_Tree_Min(mid+1, r, rch, mid+1, t));
}

void DFS1(const int& a)
{
	size[a] = 1;
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to;
		if(to == fa[a]) continue;
		fa[to] = a;
		depth[to] = depth[a] + 1;
		DFS1(to);
		size[a] += size[to];
		if(size[to] > size[son[a]]) son[a] = to;
	}
}

void DFS2(const int& a, const int& tp)
{
	top[a] = tp;
	dfn[a] = ++dfsclock;
	id[dfsclock] = a;
	if(son[a]) DFS2(son[a], tp);
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to;
		if(to == fa[a] || to == son[a]) continue;
		DFS2(to, to);
	}
	end[a] = dfsclock;
}

inline void Change(int s, int t)
{
	int f1 = top[s], f2 = top[t];
	while(f1 != f2){
		if(depth[f1] < depth[f2]){
			swap(f1, f2);
			swap(s, t);
		}
		Segment_Tree_Change(1, n, 1, dfn[f1], dfn[s]);
		s = fa[f1];
		f1 = top[s];
	}
	if(depth[s] < depth[t]) swap(s, t);
	Segment_Tree_Change(1, n, 1, dfn[t], dfn[s]);
}

inline int LCA(int s, int t)
{
	int f1 = top[s], f2 = top[t];
	while(f1 != f2){
		if(depth[f1] < depth[f2]){
			swap(f1, f2);
			swap(s, t);
		}
		s = fa[f1];
		f1 = top[s];
	}
	if(depth[s] < depth[t]) swap(s, t);
	return t;
}

inline int Query(const int& rt)
{
	// rt与首都的位置关系:
	// 1. 首都就是rt, 查询整棵树
	// 2. 首都在rt上面或者首都与rt在互不影响的两棵子树上, 查询rt的子树
	// 3. 首都在rt下面, 先找到首都在rt的哪个儿子上, 查询除了这个儿子的子树外的所有其他点
	if(rt == capital){
		// printf("CAPITAL ");
		return Segment_Tree_Min(1, n, 1, 1, n);
	}
	if(LCA(rt, capital) != rt){
		// printf("CAPITAL:%d rt:%d size:%d ans:", dfn[capital], dfn[rt], size[rt]);
		return Segment_Tree_Min(1, n, 1, dfn[rt], dfn[rt]+size[rt]-1);
	}
	for(int i = head[rt]; i; i = edges[i].next){
		int to = edges[i].to;
		if(to == fa[rt]) continue;
		if(dfn[to] <= dfn[capital] && dfn[capital] <= dfn[to] + size[to] - 1){
			// printf("		start: %d capital:%d end:%d ans: ", dfn[to], dfn[capital], dfn[to] + size[to] - 1);
			if(dfn[to]+size[to] > n) return Segment_Tree_Min(1, n, 1, 1, dfn[to]-1);
			else return min(Segment_Tree_Min(1, n, 1, 1, dfn[to]-1), Segment_Tree_Min(1, n, 1, dfn[to]+size[to], n));
		}
	}
}

#define SUBMIT
int main()
{
#ifdef SUBMIT
	freopen("bbbbb.in", "r", stdin); freopen("bbbbb.out", "w", stdout);
#endif

	Read(n); Read(m);
	int from, to, type, s, t, rt;
	for(int i = 1; i < n; i++){
		Read(from); Read(to);
		AddEdge(from, to); 
		AddEdge(to, from);
	}
	for(int i = 1; i <= n; i++) Read(value[i]);
	Read(capital);

	depth[capital] = 1;
	DFS1(capital);
	DFS2(capital, capital);
	Segment_Tree_Build(1, n, 1);

	for(int i = 1; i <= m; i++){
		Read(type);
		if(type == 1) Read(capital);
		else if(type == 2){
			Read(s); Read(t); Read(num);
			Change(s, t);
		}
		else{
			Read(rt);
			printf("%d\n", Query(rt));
		}
	}

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}