先建出来圆方树，圆点为本身的权值，方点为与之相连的圆点的最小值。
很明显答案就是询问的两点间的路径上的最小值。
考虑修改操作
(1) .圆点：直接改
(2) .方点：对每个方点开一个 (multiset) ，存储相邻的点的权值。
我们发现这样的话修改一个圆点的时候会修改很多方点，效率低。
我们将 (multiset) 改为存储儿子的权值，这样我们修改圆点的时候就只用修改相应的父亲节点了。
用树剖维护修改和查询操作就行了。注意查询时若 (lca) 是方点，还要考虑其父亲圆点。
注意 (multiset) 的删除操作的正确用法。
#include<iostream>
#include<cstdio>
#include<set>
#define lson (k<<1)
#define rson ((k<<1)|1)
using namespace std;
int n, m, q, tot, Tot, num, Top, x, y, cnt, a, b;
const int N = 400010;
int head[N], to[N], nt[N], Head[N], To[N], Nt[N], dfn[N], low[N], zhan[N], w[N], nfd[N], siz[N], son[N], top[N], dep[N], fa[N], tr[N << 2];
char opt[3];
multiset<int>s[N];
multiset<int>::iterator it;
void add(int f, int t)
{
to[++tot] = t; nt[tot] = head[f]; head[f] = tot;
}
void ADD(int f, int t)
{
To[++Tot] = t; Nt[Tot] = Head[f]; Head[f] = Tot;
}
void Tarjan(int x)
{
dfn[x] = low[x] = ++cnt; zhan[++Top] = x;
for (int i = Head[x]; i; i = Nt[i])
if (!dfn[To[i]])
{
Tarjan(To[i]); low[x] = min(low[x], low[To[i]]);
if (low[To[i]] >= dfn[x])
{
add(++num, x); add(x, num);
int t;
do
{
t = zhan[Top--]; add(num, t); add(t, num);
} while (t != To[i]);
}
}
else low[x] = min(low[x], dfn[To[i]]);
}
void dfs1(int x, int f)
{
fa[x] = f; dep[x] = dep[f] + 1; siz[x] = 1;
if (x <= n && f)s[f].insert(w[x]);
for (int i = head[x]; i; i = nt[i])
if (to[i] != f)
{
dfs1(to[i], x);
siz[x] += siz[to[i]];
if (siz[to[i]] > siz[son[x]])son[x] = to[i];
}
if (x > n)w[x] = *s[x].begin();
}
void dfs2(int x, int t)
{
top[x] = t; dfn[x] = ++cnt; nfd[cnt] = x;
if (son[x])dfs2(son[x], t);
else return;
for (int i = head[x]; i; i = nt[i])
if (to[i] != fa[x] && to[i] != son[x])dfs2(to[i], to[i]);
}
void pushup(int k)
{
tr[k] = min(tr[lson], tr[rson]);
}
void build(int k, int l, int r)
{
if (l == r)
{
tr[k] = w[nfd[l]];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid); build(rson, mid + 1, r);
pushup(k);
}
int ask(int k, int l, int r, int x, int y)
{
if (x <= l && r <= y)return tr[k];
int mid = (l + r) >> 1, res = 2e9;
if (x <= mid)res = min(res, ask(lson, l, mid, x, y));
if (mid + 1 <= y)res = min(res, ask(rson, mid + 1, r, x, y));
return res;
}
void change(int k, int l, int r, int pos, int val)
{
if (l == r)
{
tr[k] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)change(lson, l, mid, pos, val);
else change(rson, mid + 1, r, pos, val);
pushup(k);
}
int cask(int x, int y)
{
int res = 2e9;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])swap(x, y);
res = min(res, ask(1, 1, num, dfn[top[x]], dfn[x])); x = fa[top[x]];
}
if (dep[x] < dep[y])swap(x, y);
res = min(res, ask(1, 1, num, dfn[y], dfn[x]));
if (y > n)res = min(res, w[fa[y]]);
return res;
}
int main()
{
cin >> n >> m >> q; num = n;
for (int i = 1; i <= n; ++i)scanf("%d", &w[i]); w[0] = 2e9;
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &x, &y);
ADD(x, y); ADD(y, x);
}
Tarjan(1); cnt = 0; dfs1(1, 0); dfs2(1, 1); build(1, 1, num);
while (q--)
{
scanf("%s%d%d", opt, &a, &b);
if (opt[0] == 'C')
{
if (fa[a])
{
it = s[fa[a]].find(w[a]), s[fa[a]].erase(it), s[fa[a]].insert(b);
w[fa[a]] = *s[fa[a]].begin(), change(1, 1, num, dfn[fa[a]], w[fa[a]]);
}
w[a] = b; change(1, 1, num, dfn[a], b);
}
else printf("%d
", cask(a, b));
}
return 0;
}