P3979

发表于 分类于
遥远的国度

遥远的国度

在机房做树剖水题愉悦身心。

直接按照 1 为根剖分。

如果说现有根是询问点，输出全局最小。

如果说现有根是不在询问点的子树中，我们就直接输出询问点的子树最小值。

如果说现有根在询问点的子树中，我们需要找到询问点的一个儿子，这个儿子是现有根的祖先。然后把这个儿子中的子树数据剔除计算最小值。

那么主要问题是如何在规定复杂度下找到这个儿子。

其实可以从现有根直接在链上跳啊跳，跳到某一个链的顶端的时候，发现自己头上的那个链包含了询问点，那么这个时候判断自己的父亲。如果说，巧了，这个父亲就是询问点，那么很显然已经找到这个轻儿子了，直接返回即可。反之，说明这个点不在询问点的轻儿子子树里，那就只能输出重儿子了。记得特判一开始两个点就在同一条链上的情况。

时间复杂度 $O(n\log^2 n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e6,inf=(1ll<<33);

ll n,m,u,v,w,rt,op,tot,cnt;

ll ver[N*2+5],nxt[N*2+5],head[N*2+5];

ll dt[N+5],fa[N+5],siz[N+5],top[N+5],id[N+5],wt[N+5],a[N+5],hs[N+5];

struct sgt{
	ll mi,lazchg;
	#define mi(x) tree[x].mi
	#define lazchg(x) tree[x].lazchg
}tree[N*4+5];

inline void build(ll p,ll l,ll r) {
	if(l==r) {mi(p)=wt[l];return;}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	mi(p)=min(mi(p<<1),mi(p<<1|1));
}

inline void spread(ll p) {
	if(lazchg(p)) {
		mi(p<<1)=lazchg(p);lazchg(p<<1)=lazchg(p);
		mi(p<<1|1)=lazchg(p);lazchg(p<<1|1)=lazchg(p);
		lazchg(p)=0;
	}
}

inline void modify(ll p,ll lp,ll rp,ll l,ll r,ll k) {
	if(lp>=l&&rp<=r) {
		mi(p)=k;lazchg(p)=k;
		return;
	}
	ll mid=(lp+rp)>>1;spread(p);
	if(l<=mid) modify(p<<1,lp,mid,l,r,k);
	if(r>mid) modify(p<<1|1,mid+1,rp,l,r,k);
	mi(p)=min(mi(p<<1),mi(p<<1|1));
}

inline ll getmi(ll p,ll lp,ll rp,ll l,ll r) {
	if(lp>=l&&rp<=r) {return mi(p);}
	ll mid=(lp+rp)>>1;spread(p);
	if(l>mid) return getmi(p<<1|1,mid+1,rp,l,r);
	if(r<=mid) return getmi(p<<1,lp,mid,l,r);
	return min(getmi(p<<1|1,mid+1,rp,l,r),getmi(p<<1,lp,mid,l,r));
}

inline void dfs(ll p,ll fath) {
	siz[p]=1;dt[p]=dt[fath]+1;fa[p]=fath;
	for(ll i=head[p];i;i=nxt[i]) {
		if(ver[i]==fath) continue;
		dfs(ver[i],p);
		siz[p]+=siz[ver[i]];
		if(siz[ver[i]]>siz[hs[p]]) hs[p]=ver[i];
	}
}

inline void dfs_(ll p,ll fath,ll topf) {
	id[p]=++cnt;wt[cnt]=a[p];top[p]=topf;
	if(hs[p]) {
		dfs_(hs[p],p,topf);
		for(ll i=head[p];i;i=nxt[i]) {
			if(ver[i]==fath||ver[i]==hs[p]) continue;
			dfs_(ver[i],p,ver[i]);
		}
	}
}

inline void chgpath(ll x,ll y,ll k) {
	while(top[x]!=top[y]) {
		if(dt[top[x]]<dt[top[y]]) swap(x,y);
		modify(1,1,n,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(id[x]>id[y]) swap(x,y);
	modify(1,1,n,id[x],id[y],k);
}

inline ll qsubmi(ll p) {
	return getmi(1,1,n,id[p],id[p]+siz[p]-1);
}

inline ll findson(ll x,ll y) {
	if(top[x]==top[y]) return hs[y];
	while(top[fa[top[x]]]!=top[y]) x=fa[top[x]];
	if(fa[top[x]]==y) return top[x];
	return hs[y];
}

inline void addedge(ll u,ll v) {
	ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

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

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {
	write(x);putchar('\n');
}

int main() {
	
	n=read();m=read();
	
	for(ll i=1;i<n;i++) {
		u=read();v=read();
		addedge(u,v);addedge(v,u);
	}
	
	for(ll i=1;i<=n;i++) a[i]=read();
	
	rt=read();
	
	dfs(1,0);dfs_(1,0,1);build(1,1,n);
	
	while(m--) {
		op=read();
		if(op==1) {rt=read();}
		if(op==2) {
			u=read();v=read();w=read();
			chgpath(u,v,w);
		}
		if(op==3) {
			u=read();
			if(rt==u) {
				writeln(qsubmi(1));
			}
			else
			if(id[rt]>id[u]&&id[rt]<=id[u]+siz[u]-1) {
				v=findson(rt,u);
				ll ans=inf;
				if(1<=id[v]-1) ans=min(ans,getmi(1,1,n,1,id[v]-1));
				if(id[v]+siz[v]<=n) ans=min(ans,getmi(1,1,n,id[v]+siz[v],n));
				writeln(ans);
			}
			else {
				writeln(qsubmi(u));
			}
		}
	}
	
	return 0;
}