$50$ 分，TLE on #2。

做法是树链剖分。

#include<bits/stdc++.h>
using namespace std;
int ig[100005], dfn[100005], low[100005], vl[114514];
int n, m, a1, a2, cnt, ign, ans, ccnt, qq;
vector<int> G[100005], BCC[100005], CST[100005];
stack<int> s;
queue<int> q;
void tarjan(int u){
	dfn[u] = low[u] = ++cnt;
	int sn = 0;
	s.push(u);
	for (auto &v : G[u]){
		if (!dfn[v]){
			sn++;
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]){
				ccnt++;
				while (!s.empty()){
					int vv = s.top();
					s.pop();
					CST[n + ccnt].push_back(vv);
					CST[vv].push_back(n + ccnt);
					BCC[ccnt].push_back(vv);
				//	cerr << vv << "<->" << n + ccnt << "\n";
					if (v == vv)
						break;
				}
				BCC[ccnt].push_back(u);
				CST[n + ccnt].push_back(u);
            	CST[u].push_back(n + ccnt);
			//	cerr << u << "<->" << n + ccnt << "\n";
			}
		}else
			low[u] = min(low[u], dfn[v]);
	}
}
long long a[100005];
int fa[100005],hs[100005],sz[100005],top[100005],ddfn[100005],rdfn[100005],dep[100005];
int vst;
void dfs(int u,int fat) {
	fa[u]=fat;
	sz[u]=1;
	dep[u]=dep[fat]+1;
	for(auto &v:CST[u]) {
		if(v==fat)continue;
		dfs(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[hs[u]])hs[u]=v;
	}
}
void cut(int u,int tp) {
	ddfn[u]=++vst;
	rdfn[vst]=u;
	top[u]=tp;
	if(hs[u]) {
		cut(hs[u],tp);
		for(auto &v:G[u])if(v!=fa[u]&&v!=hs[u])cut(v,v);
	}
}
long long tr[800020],trr[800020];
void pup(int u) {
	tr[u]=tr[u<<1]+tr[u<<1|1];
	trr[u]=min(trr[u<<1],trr[u<<1|1]);
}
void build(int u,int le,int ri) {
	if(le==ri) {
		tr[u]=trr[u]=a[rdfn[le]];
		return;
	}
	int mid=(le+ri)>>1;
	build(u<<1,le,mid);
	build(u<<1|1,mid+1,ri);
	pup(u);
}
bool inr(int le,int ri,int L,int R) {
	return (L<=le)&&(ri<=R);
}
bool otr(int le,int ri,int L,int R) {
	return (le>R)||(ri<L);
}
long long query(int u,int le,int ri,int L,int R) {
//	cout << trr[u] << "\n";
	if(inr(le,ri,L,R))return trr[u];
	else if(!otr(le,ri,L,R)) {
		int mid=(le+ri)>>1;
		return min(query(u<<1,le,mid,L,R),query(u<<1|1,mid+1,ri,L,R));
	}
	return INT_MAX;
}
long long qry(int x,int y) {
	long long ans=INT_MAX;
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=min(ans,query(1,1,n+ccnt,ddfn[top[x]],ddfn[x]));
		x=fa[top[x]];
	}
	return min(ans,query(1,1,n+ccnt,min(ddfn[x],ddfn[y]),max(ddfn[x],ddfn[y])));
}
void update(int u,int le,int ri,int ft,long long x) {
	int mid=(le+ri)>>1;
	if(le==ri){
		tr[u]=trr[u]=x;
		return;
	}
	if(ft<=mid)update(u<<1,le,mid,ft,x);
	else update(u<<1|1,mid+1,ri,ft,x);
	pup(u);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> qq;
	for(int i=1; i<=n; i++)cin>>a[i];
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]){
			tarjan(i);
			s.pop();
		}
	for (int i = n + 1; i <= n + ccnt; i++)
		a[i] = INT_MAX;
	int r = 1;
	for(int i=1;i<=n+ccnt;i++)sort(CST[i].begin(),CST[i].end(),[](int x,int y){return a[x]<a[y];});
	dfs(r,0);
	cut(r,0);
	build(1,1,n+ccnt);
	while(qq--) {
		string ord;
		cin>>ord;
		if(ord=="C"){
			int u,v;
			cin>>u>>v;
			update(1,1,n+ccnt,ddfn[u],v);
		}else if(ord=="A"){
			int u,v;
			cin>>u>>v;
			long long ans = qry(u, v);
			for (auto w : CST[u])
				if (w > n){
					for (auto x : BCC[w - n])
						if (x != u){
						//	cout << x << "\n";
							ans = min(ans, qry(x, x));
						}
				}
			for (auto w : CST[v])
				if (w > n){
					for (auto x : BCC[w - n])
						if (x != v)
							ans = min(ans, qry(x, x));
				}
			cout<<ans<<'\n';
		}
	}
}