分析
可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。
从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的权值，修改圆点权值时直接 erase 再 insert 一下，如果发生了变化在线段树上单点修改即可。
这样子有一个问题，就是当圆方树是一个菊花的形状时每次修改都是 $\mathcal{O}(n)$ 级别的，会 GG。注意到广义圆方树上圆方点是相间的，所以方点的 multiset 中可以只维护子节点的权值，在查询时如果 LCA 为方点就把它的父节点也算上即可。
写起来挺休闲的，只要码一堆板子上去就行了，没有什么细节。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10;
int n,m,Q,w[N],tot;
vector<int> E[N],T[N];
multiset<int> S[N];
namespace Tarjan {
int dfn[N],low[N],tim=0;
int sta[N],top=0;
void tarjan(int u) {
dfn[u]=low[u]=++tim,sta[++top]=u;
for (int v:E[u]) {
if (!dfn[v]) {
tarjan(v),low[u]=min(low[u],low[v]);
if (low[v]>=dfn[u]) {
++tot,T[tot].emplace_back(u),T[u].emplace_back(tot);
while ("Nin Diao Da Wo") {
int t=sta[top--];
T[tot].emplace_back(t),T[t].emplace_back(tot);
if (t==v) break; // 注意这里不是 t==u
}
}
}
else low[u]=min(low[u],dfn[v]);
}
}
} // namespace Tarjan
int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],pos[N],tim=0;
void dfs1(int u,int f) {
dep[u]=dep[fa[u]=f]+1,sz[u]=1;
if (u<=n&&f) S[f].insert(w[u]);
for (int v:T[u]) {
if (v==f) continue;
dfs1(v,u),sz[u]+=sz[v];
if (sz[v]>sz[hson[u]]) hson[u]=v;
}
}
void dfs2(int u,int anc) {
top[u]=anc,dfn[u]=++tim,pos[tim]=u;
if (hson[u]) dfs2(hson[u],anc);
for (int v:T[u])
if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
}
#define ls (o<<1)
#define rs (o<<1|1)
int minv[N<<2];
void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
void build(int o,int l,int r) {
if (l==r) {
minv[o]=pos[l]<=n?w[pos[l]]:*S[pos[l]].begin();
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
if (l==r) { minv[o]=w; return; }
int mid=(l+r)>>1;
if (p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return minv[o];
int mid=(l+r)>>1,res=2e9;
if (ql<=mid) res=min(res,query(ls,l,mid,ql,qr));
if (qr>mid) res=min(res,query(rs,mid+1,r,ql,qr));
return res;
}
#undef ls
#undef rs
void modify(int u,int v) {
if (fa[u]) {
S[fa[u]].erase(S[fa[u]].find(w[u]));
S[fa[u]].insert(v);
modify(1,1,tot,dfn[fa[u]],*S[fa[u]].begin());
}
w[u]=v,modify(1,1,tot,dfn[u],v);
}
int query(int u,int v) {
int res=2e9;
while (top[u]!=top[v]) {
if (dep[top[u]]<dep[top[v]]) swap(u,v);
res=min(res,query(1,1,tot,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if (dep[u]<dep[v]) swap(u,v);
res=min(res,query(1,1,tot,dfn[v],dfn[u]));
if (v>n) res=min(res,w[fa[v]]);
return res;
}
int main() {
n=read(),m=read(),Q=read();
for (int i=1;i<=n;++i) w[i]=read();
for (int i=1;i<=m;++i) {
int u=read(),v=read();
E[u].emplace_back(v),E[v].emplace_back(u);
}
tot=n,Tarjan::tarjan(1); dfs1(1,0),dfs2(1,1); build(1,1,tot);
while (Q--) {
char s[2]; scanf("%s",s);
if (s[0]=='C') { int u=read(),v=read(); modify(u,v); }
else { int u=read(),v=read(); printf("%d\n",query(u,v)); }
}
return 0;
}