T了，求卡常

#include<bits/stdc++.h>
#define inf (0x3f3f3f3f)
using namespace std;

const int maxn = 9e5 + 10;

#define gc getchar()
int rd(){
	int x = 0; char ch = gc;
	for (; !isdigit(ch); ch = gc);
	for (; isdigit(ch); ch = gc) x = x * 10 + ch - '0';
	return x;
}

int h[maxn], rep = 1, nx[maxn], to[maxn];
void ad(int u, int v){ to[++rep] = v; nx[rep] = h[u]; h[u] = rep;}
int w[maxn];

int n, m, q;

int dfn1[maxn], low1[maxn], tim1, cnt;
stack<int> st;
void tarjan(int x, int fa){
	dfn1[x] = low1[x] = ++tim1; st.push(x);
	int cntson = 0;
	for (int i = h[x]; i; i = nx[i]){
		if(to[i] == fa) continue; cntson++;
		if(!dfn1[to[i]]){
			tarjan(to[i], x); low1[x] = min(low1[x], low1[to[i]]);
			
			if(low1[to[i]] < dfn1[x]) continue;
			
			++cnt;
			for (int flg = 1; flg; st.pop()){
				if(st.top() == to[i]) flg = 0;
				ad(cnt, st.top() + n); ad(st.top() + n, cnt);w[st.top() + n] = w[st.top()];
			}
			ad(cnt, x + n); ad(x + n, cnt); w[x + n] = w[x];
			
		}else low1[x] = min(low1[x],dfn1[to[i]]);
	}
	if(!fa && !cntson) w[x + n] = w[x];
}

multiset<int> regw[maxn];
int f[maxn], son[maxn], siz[maxn], dep[maxn];
void dfs1(int x, int fa){
	f[x] = fa; siz[x] = 1; dep[x] = dep[fa] + 1;
	for (int i = h[x]; i; i = nx[i]){
		if(to[i] == fa) continue;
		dfs1(to[i], x);
		siz[x] += siz[to[i]];
		if(!son[x] || siz[son[x]] < son[to[i]]) son[x] = to[i];
	}
	
	if(x > 2 *n){
		for (int i = h[x]; i; i = nx[i]){
			if(to[i] == fa) continue;
			regw[x].insert(w[to[i]]);
		}
		w[x] = *regw[x].begin();
	}
}

int dfn2[maxn], idfn[maxn], tim2, tp[maxn];
void dfs2(int x, int top){
	dfn2[x] = ++tim2; idfn[tim2] = x; tp[x] = top;
	for (int i = h[x]; i; i = nx[i]){
		if(to[i] == f[x] || to[i] != son[x]) continue;
		dfs2(to[i], top);
	}
	
	for (int i = h[x]; i; i = nx[i]){
		if(to[i] == f[x] || to[i] == son[x]) continue;
		dfs2(to[i], to[i]);
	}
}

int t[maxn];
#define mid ((l+r) >> 1)
#define ls (x << 1)
#define rs (x << 1| 1)
void up(int x){t[x] = min(t[ls], t[rs]);}
void build(int x, int l, int r){
	if(l == r) return t[x] = w[idfn[l]], void();
	build(ls, l, mid); build(rs, mid+1, r);
	up(x);
}
int sig(int x, int l, int r, int L, int R){
	if(L <= l && r <= R) return t[x]; int ans = inf;
	if(L <= mid) ans = min(ans, sig(ls, l, mid, L, R));
	if(R > mid) ans = min(ans, sig(rs, mid+1, r, L, R));
	return ans;
}
void chg(int x, int l, int r, int df){
	if(l == r) return t[x] = w[idfn[df]], void();
	if(df <= mid) chg(ls, l, mid, df);
	else chg(rs, mid+1, r, df);
	up(x);
}

int qryc(int x, int y){
	int ans = inf;
	while(tp[x] != tp[y]){
		if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
		ans = min(ans, sig(1, 1, tim2, dfn2[tp[x]], dfn2[x])); x = f[tp[x]];
	}
	if(dep[x] < dep[y]) swap(x, y); ans = min(ans, sig(1, 1, tim2, dfn2[y], dfn2[x]));
	if(y > 2 * n) ans = min(ans, sig(1, 1, tim2, dfn2[f[y]], dfn2[f[y]]));
	return ans;
}

signed main(){
	cin >> n >> m >> q;
	cnt = 2*n;
	
	for (int i = 1; i <= n; i++) w[i] = rd();
	for (int i = 1, u, v; i <= m; i++) u = rd(), v = rd(), ad(u, v), ad(v, u);
	
	tarjan(1, 0);
	
	dfs1(1 + n, 0);
	dfs2(1 + n, 1 + n);
	
	build(1, 1, tim2);
	
	for (int i = 1, a, b, wi; i <= q; i++){
		char ch; cin >> ch;
		if(ch == 'A'){
			a = rd(); b = rd();
			a = a + n; b = b + n;
			printf("%d\n", qryc(a, b));
		}else if(ch == 'C'){
			a = rd(); wi = rd();
			a = a + n; int fa = f[a];
			
			if(fa) {
				auto it = regw[fa].lower_bound(w[a]);
				regw[fa].erase(it);
				regw[fa].insert(wi);
				w[fa] = *regw[fa].begin();
			}
			
			w[a] = wi;
			
			chg(1, 1, tim2, dfn2[a]);
			if(fa) chg(1, 1, tim2, dfn2[fa]);
		}
	}
	return 0;
}

cf记录