一般图，带修求所有简单路径代价。
简单路径，不能经过同一个点两次，那么每个V-DCC出去就不能再回来了。
所以可以圆方树，然后方点维护一下V-DCC内的最小值。
那么，从任意一个割点进入这个DCC，必然可以绕一圈再从另一个割点出去。
所以，路径上的最小值，就是圆方树路径上的最小值。方点的最小值就是在这个DCC中走一走得到的。
树链剖分+线段树维护路径
用堆维护方点四周的圆点的最小值。然后更新。
一个问题是：
更新一个割点圆点，会影响到四周所有的方点。暴力更新，菊花图直接TLE
这样更新：
方点只维护圆方树上儿子圆点的最值。
这样，每次修改圆点，只要修改father的方点的值即可。
查询路径的时候，如果LCA是方点，那么把这个方点的father的值也取min即可。
圆点就无所谓了。LCA自己一定会取到的。
代码：
#include<bits/stdc++.h>
#define reg register int
#define mid ((l+r)>>1)
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=2e5+;
const int inf=0x3f3f3f3f;
int n,m,q;
struct node{
int nxt,to;
}e[*N],bian[*N];
int hd[N],pre[N];
int cnt1,cnt2;
void _add(int x,int y){
bian[++cnt1].nxt=pre[x];
bian[cnt1].to=y;
pre[x]=cnt1;
}
void add(int x,int y){
e[++cnt2].nxt=hd[x];
e[cnt2].to=y;
hd[x]=cnt2;
}
struct heap{
priority_queue<int,vector<int>,greater<int> >h,d;
int top(){
while(h.size()&&d.size()&&h.top()==d.top()){
h.pop();d.pop();
}
if(h.empty()) return inf;
return h.top();
}
void push(int c){
h.push(c);
}
void dele(int c){
d.push(c);
}
}f[N];
int w[N];
int tot,df;
int dfn[N],low[N],sta[N],tp;
void tarjan(int x){
dfn[x]=low[x]=++df;
sta[++tp]=x;
for(reg i=pre[x];i;i=bian[i].nxt){
int y=bian[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
++tot;//fang
w[tot]=inf;//warning!!!
int z;
do{
z=sta[tp--];
add(tot,z);add(z,tot);
}while(z!=y);
add(x,tot);add(tot,x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int dep[N],fa[N],top[N],fdfn[N],son[N],sz[N];
void dfs1(int x,int d){
dep[x]=d;
sz[x]=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa[x]) continue;
fa[y]=x;
dfs1(y,d+);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
if(x>n){//a fang
f[x].push(w[y]);
w[x]=min(w[x],w[y]);
}
}
}
void dfs2(int x){
dfn[x]=++df;
fdfn[df]=x;
if(!top[x]) top[x]=x;
if(son[x]) top[son[x]]=top[x],dfs2(son[x]);
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa[x]) continue;
if(y==son[x]) continue;
dfs2(y);
}
}
int mi[*N];
void pushup(int x){
mi[x]=min(mi[x<<],mi[x<<|]);
}
void build(int x,int l,int r){
if(l==r){
mi[x]=w[fdfn[l]];return;
}
build(x<<,l,mid);
build(x<<|,mid+,r);
pushup(x);
}
void chan(int x,int l,int r,int to,int c){
if(l==r){
mi[x]=c;return;
}
if(to<=mid) chan(x<<,l,mid,to,c);
else chan(x<<|,mid+,r,to,c);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return mi[x];
}
int ret=inf;
if(L<=mid) ret=min(ret,query(x<<,l,mid,L,R));
if(mid<R) ret=min(ret,query(x<<|,mid+,r,L,R));
return ret;
}
int wrk(int x,int y){
int ret=inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret=min(ret,query(,,tot,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
ret=min(ret,query(,,tot,dfn[y],dfn[x]));
if(y>n) ret=min(ret,w[fa[y]]);
return ret;
}
int main(){
rd(n);rd(m);rd(q);
for(reg i=;i<=n;++i)rd(w[i]);
int x,y;
for(reg i=;i<=m;++i){
rd(x);rd(y);
_add(x,y);_add(y,x);
}
tot=n;
tarjan();
memset(dfn,,sizeof dfn);
df=;
dfs1(,);
dfs2();
build(,,tot);
char ch[];
while(q--){
scanf("%s",ch+);
if(ch[]=='A'){
rd(x);rd(y);
printf("%d\n",wrk(x,y));
}
else{
rd(x);rd(y);
int ff=fa[x];
f[ff].dele(w[x]);
f[ff].push(y);
int tmp=f[ff].top();
chan(,,tot,dfn[ff],tmp);
w[ff]=tmp;//no use in fact
w[x]=y;
chan(,,tot,dfn[x],y);
}
}
return ;
} }
int main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2018/11/30 16:10:40
*/