调一个上午了，圆方树+树剖Qwq

码量真的大啊O.o

#include<bits/stdc++.h>
#define inf 1e9
#define int long long
using namespace std;
const int maxn = 100100;
vector<int> vec[maxn], vec_new[maxn];
struct node{
	int from, to;
}edge[maxn];
int w[maxn], loc[maxn], tot;
int dfn_t[maxn], low_t[maxn], ti, sta[maxn], top;
int tarjan(int index = 1) {
	dfn_t[index] = low_t[index] = ++ti;
	sta[++top] = index;
	for(int i=0; i<vec[index].size(); ++i) {
		if(!dfn_t[vec[index][i]]) {
			tarjan(vec[index][i]);
			if(low_t[vec[index][i]] >= dfn_t[index]) {
				++tot;
				loc[tot] = tot;
				w[tot] = inf;
				while(sta[top+1] != vec[index][i]) {
					vec_new[tot].push_back(sta[top]);
					vec_new[sta[top]].push_back(tot);
					loc[sta[top]] = tot;
					w[tot] = min(w[tot], w[sta[top]]);
					top--;
				}
				vec_new[tot].push_back(index);
				vec_new[index].push_back(tot);
				loc[index] = tot; 
				w[tot] = min(w[tot], w[index]);
			}
			low_t[index] = min(low_t[index], low_t[vec[index][i]]);
		} else{
			low_t[index] = min(low_t[index], dfn_t[vec[index][i]]); 
		}
	}
}
int fa[maxn], size[maxn], tp[maxn], dfn[maxn], w_new[maxn];
int wson[maxn], son[maxn], depth[maxn];
void dfs1(int index = 1, int back = 0) {
//	cout << index << " 1" << endl;
	size[index] = 1;
	for(int i = 0; i<vec_new[index].size(); ++i) {
		if(vec_new[index][i] == back) continue;
		dfs1(vec_new[index][i], index);
		size[index] += size[vec_new[index][i]];
		if(son[index] == 0 || size[vec_new[index][i]] > size[son[index]]) {
			son[index] = vec_new[index][i];
			wson[index] = w[vec_new[index][i]];
		}
	}
}
void dfs2(int index=1, int back = 0, int t = 1) {
//	cout << index << " 2" << endl;
	dfn[index] = ++ti;
	tp[index] = t;
	depth[index] = depth[back]+1;
	if(son[index]) {
		dfs2(son[index], index, t);
		w_new[dfn[son[index]]] = wson[index];
	}
	for(int i=0; i<vec_new[index].size(); ++i) {
		if(vec_new[index][i] == son[index] || vec_new[index][i] == back) {
			continue;
		}
		dfs2(vec_new[index][i], index, vec_new[index][i]);
		w_new[dfn[vec_new[index][i]]] = w[vec_new[index][i]];
	}
}
int tree[maxn<<3];
void build(int l, int r, int index) {
	if(l == r) {
		tree[index] = w_new[l];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, index*2); build(mid+1, r, index*2+1);
	tree[index] = min(tree[index*2], tree[index*2+1]);
}
int query(int l, int r, int index, int left, int right) {
	if(l >= left && r <= right) {
		return tree[index];
	}
	if(left > r || right < l) {
		return inf;
	}
	int mid = l + r >> 1;
	return min(query(l, mid, index*2, left, right), query(mid+1, r, index*2+1, left, right));	
}
int n, m, q; 
void modify(int l, int r, int index, int which) {
	if(which > r || which < l) {
		return;
	}
	if(l == r) {
		tree[which] = w_new[which];
		return;
	}
	int mid = l + r >> 1;
	modify(l, mid, index*2, which);
	modify(mid+1, r, index*2+1, which);
	tree[index] = min(tree[index*2], tree[index*2+1]);
}
int ask(int l, int r) {
	int minn = inf;
	while(tp[l] != tp[r]) {
		if(depth[tp[l]] > depth[tp[r]]) {
			swap(l, r);
		}
		minn = min(minn, query(1, tot, 1, dfn[tp[r]], dfn[r]));
		r = fa[tp[r]];
	}
	if(depth[l] > depth[r]) {
		swap(l, r);
	}
	minn = min(minn, query(1, tot, 1, dfn[l], dfn[r]));
	return minn;
}
signed main() {
//	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q; tot = n; for(int i=1; i<=n; ++i) {
		cin >> w[i];
	}
	for(int i=1; i<=m; ++i) {
		int u, v; cin >> u >> v; edge[i].from = u; edge[i].to = v;
		vec[u].push_back(v); vec[v].push_back(u);
	}
	tarjan();
	for(int i=1; i<=m; ++i) {
		if(loc[edge[i].from] != loc[edge[i].to]) {
			vec_new[edge[i].from].push_back(edge[i].to);
			vec_new[edge[i].to].push_back(edge[i].from);
		}
	}
//	for(int i=1; i<=tot; ++i) {
//		cout << i << "L";
//		for(int j=0; j<vec_new[i].size(); ++j) {
//			cout << vec_new[i][j] << " ";
//		}
//		cout << endl;
//	}
//	return 0;
	ti = 0;
//	cout << 114514;
//	for(int i=1; i<=tot; ++i) {
//		cout << w[i] << ' ';
//	}
//	cout << endl;
	memset(tree, 0x3f, sizeof tree);
	dfs1(); dfs2(); build(1, tot, 1);
	while(q--) {
		char ch; cin >> ch;
		if(ch == 'C') {
			int a, w; cin >> a >> w;
			w_new[dfn[a]] = w;
			w_new[dfn[loc[a]]] = w;
			modify(1, tot, 1, dfn[a]);
			modify(1, tot, 1, dfn[loc[a]]);
		} else if(ch == 'A') {
			int a, b; cin >> a >> b;
			cout << ask(a, b) << endl; 
		}
	}
	return 0;
}