兔队NB！

RT，#3 TLE2s，按理来说树剖$O(qlog^2n)$的复杂度应该不会T啊。。。有人能康康吗qwq

#include<iostream>
#include<cstring>
#include<vector>
#include<set>
const int M=1e5+5,Q=2e5+5;
std::vector<int>T[M],G[Q];
int n,m,q,dfc,cnt,tp,st[M],dfn[M],low[M];
int N,d[Q],f[Q],id[Q],siz[Q],top[Q],son[Q],val[Q],zkw[Q<<2];
std::multiset<int>t[Q];
int min(const int x,const int y){
	return x>y?y:x;
}
void Tarjan(int u){
	dfn[u]=low[u]=++dfc;
	st[++tp]=u;
	for(auto v:T[u]){
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[u]);
			if(low[v]==dfn[u]){
				++cnt;
				for(int x=0;x!=v;--tp){
					x=st[tp];
					G[x].push_back(cnt);
					G[cnt].push_back(x);
				}
				G[u].push_back(cnt);
				G[cnt].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
void DFS1(int u){
	siz[u]=1;
	d[u]=d[f[u]]+1;
	for(auto v:G[u])if(v!=f[u]){
		f[v]=u;
		DFS1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void DFS2(int u,int tp){
	top[u]=tp;id[u]=++dfc;
	if(!son[u])return;
	DFS2(son[u],tp);
	for(auto v:G[u]){
		if(v!=f[u]&&v!=son[u])DFS2(v,v);
	}
}
inline void modify(int x,int v){
	zkw[x+=N]=v;
	for(x>>=1;x;x>>=1){
		zkw[x]=min(zkw[x<<1],zkw[x<<1|1]);
	}
}
inline int query(int s,int t){
	int ans=0x7fffffff;
	for(s+=N-1,t+=N+1;s^t^1;s>>=1,t>>=1){
		if(~s&1)ans=min(ans,zkw[s^1]);
		if(t&1)ans=min(ans,zkw[t^1]);
	}
	return ans;
}
inline void init(){
	int i;
	cnt=n;Tarjan(1);dfc=0;
	DFS1(1);DFS2(1,1);
	for(N=1;N<=cnt+1;N<<=1);
	memset(zkw,0x3f,sizeof zkw);
	for(i=1;i<=n;++i){
		if(f[i])t[f[i]].insert(val[i]);
	}
	for(i=n+1;i<=cnt;++i)val[i]=*t[i].begin();
	for(i=1;i<=cnt;++i)zkw[N+id[i]]=val[i];
	for(i=N-1;i;--i)zkw[i]=min(zkw[i<<1],zkw[i<<1|1]);
}
signed main(){
	int i;
	std::cin>>n>>m>>q;
	for(i=1;i<=n;++i)std::cin>>val[i];
	for(i=1;i<=m;++i){
		int u,v;
		std::cin>>u>>v;
		T[u].push_back(v);
		T[v].push_back(u);
	}
	init();
	for(i=1;i<=q;++i){
		char s;int x,y;
		std::cin>>s>>x>>y;
		if(s=='C'){
			if(f[x]){
				int u=f[x];
				t[u].erase(t[u].upper_bound(val[x]));
				t[u].insert(y);
				i=*t[u].begin();
				if(val[u]!=i)modify(id[u],val[u]=i);
			}
			modify(id[x],val[x]=y);
		}
		else{
			int ans=0x7fffffff;
			while(top[x]!=top[y]){
				if(d[top[x]]<d[top[y]])x^=y^=x^=y;
				ans=min(ans,query(id[top[x]],id[x]));
				x=f[top[x]];
			}
			if(d[x]>d[y])x^=y^=x^=y;
			ans=min(ans,query(id[x],id[y]));
			if(x>n)ans=min(ans,val[f[x]]);
			printf("%d\n",ans);
		}
	}
}