题目大意
给定(n)个点(m)条边的无向连通图，无重边
每个点有点权
两个操作：
1.单点点权修改
2.询问从x到y的简单路径中，路径经过点的最小值的最小值时多少
（简单路径指经过每一个点至多一次）
分析
使用点双连通分量转化为树
（点双连通分量表示该连通分量中，去掉任意一个点都不回使其不连通）
这样子
当我们经过一个点双连通分量的至少两个点时，可以拿到这个点双内的最小权值
证明：
1.当只经过一个点时，经过的是一个割点，只经过一个点的情况下，不能进入该点双
2.当经过至少两个点时
①该点双只有两个点，显然成立
②该点双有(ge 3)个点时，设最开始经过a，最后经过的点是b，该点双的最小值为c
当c为a或者b时，成立
否则，一定存在一条从a-c-b的路径
证明：
因为是点双，所以a-c,a-b,c-b的路径一定都是存在的
假设不存在从a-c-b的路径
说明任选一个a-c路径，所有b-c路径都与它有交
若交点有两个，则可以从a出发，走最近的交点到c，然后走另一个交点去b
否则只有一个交点，该点为b-c的必经点，删除后导致点双不连通，与定义矛盾
做法
类似圆方树的方法
点双中间加个特殊点
这篇博客挺好的
修改时不能全改（儿子多）
那就只改父亲
特判lca为特殊的情况，此时经过了该点双至少两个点
而点双中特殊点的父亲那个点并没有统计到
solution
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <functional>
#include <algorithm>
#include <queue>
using namespace std;
const int M=2e5+7;
const int INF=1e9+7;
inline int ri(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
}
int n,m,q;
int val[M];
struct vec{
int g[M],te;
struct edge{
int y,nxt;
edge(int _y=0,int _nxt=0){y=_y,nxt=_nxt;}
}e[M<<1];
vec(){memset(g,0,sizeof g);te=0;}
inline void push(int x,int y){e[++te]=edge(y,g[x]);g[x]=te;}
inline void push2(int x,int y){push(x,y);push(y,x);}
inline int& operator () (int x){return g[x];}
inline edge& operator [] (int x){return e[x];}
}e;
struct Heap{
priority_queue<int,vector<int>,greater<int> >q,ers;
inline void ins(int d){q.push(d);}
inline void del(int d){ers.push(d);}
int top(){
while(!ers.empty()&&q.top()==ers.top()) q.pop(),ers.pop();
return q.top();
}
};
namespace Seg{
int a[524299];
int n;
inline void pushup(int x){a[x]=min(a[x<<1],a[x<<1|1]);}
void ins(int x,int l,int r,int to,int d){
if(l==r){
a[x]=d;
return;
}
int mid=l+r>>1;
if(to<=mid) ins(x<<1,l,mid,to,d);
else ins(x<<1|1,mid+1,r,to,d);
pushup(x);
}
int get(int x,int l,int r,int tl,int tr){
if(tl<=l&&r<=tr) return a[x];
int mid=l+r>>1;
if(tr<=mid) return get(x<<1,l,mid,tl,tr);
if(mid<tl) return get(x<<1|1,mid+1,r,tl,tr);
return min(get(x<<1,l,mid,tl,tr),get(x<<1|1,mid+1,r,tl,tr));
}
void ins(int x,int d){ins(1,1,n,x,d);}
int get(int x,int y){return get(1,1,n,x,y);}
int get(int x){return get(1,1,n,x,x);}
}
namespace Tr{
vec e;
Heap h[M];
int pre[M],dep[M];
int sz[M],son[M];
int top[M],tdfn;
int tid[M],pid[M];
void dfs1(int x){
int p,y;
sz[x]=1; son[x]=0;
for(p=e(x);p;p=e[p].nxt)
if((y=e[p].y)!=pre[x]){
dep[y]=dep[x]+1;
pre[y]=x;
dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]) son[x]=y;
}
}
void dfs2(int x){
int p,y;
pid[tid[x]=++tdfn]=x;
if(y=son[x]){
top[y]=top[x];
dfs2(y);
}
for(p=e(x);p;p=e[p].nxt)
if((y=e[p].y)!=pre[x]&&y!=son[x]){
top[y]=y;
dfs2(y);
}
}
void split(){
pre[1]=0;dep[1]=1;
dfs1(1);
top[1]=1;tdfn=0;
dfs2(1);
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=pre[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void mdf(int x,int pr,int nw){
Seg::ins(tid[x],nw);
if(pre[x]==0) return;
if(pr>0) h[pre[x]].del(pr);
h[pre[x]].ins(nw);
Seg::ins(tid[pre[x]],h[pre[x]].top());
}
int get(int x,int y){
int lca=LCA(x,y),res=INF;
for(;dep[top[x]]>dep[lca];x=pre[top[x]])
res=min(res,Seg::get(tid[top[x]],tid[x]));
if(dep[x]>dep[lca])
res=min(res,Seg::get(tid[lca]+1,tid[x]));
for(;dep[top[y]]>=dep[lca];y=pre[top[y]])
res=min(res,Seg::get(tid[top[y]],tid[y]));
if(dep[y]>=dep[lca])
res=min(res,Seg::get(tid[lca],tid[y]));
if(lca>n&&pre[lca]) res=min(res,Seg::get(tid[pre[lca]]));
return res;
}
void push(int x,int y){e.push2(x,y);}
}
namespace G{
vec e;
int dfn[M],low[M],tdfn;
int stack[M],Top;
int cnt;
void BCC(int x,int fr){
int p,y;
dfn[x]=low[x]=++tdfn;
stack[++Top]=x;
for(p=e(x);p;p=e[p].nxt)
if((y=e[p].y)!=fr){
if(dfn[y]) low[x]=min(low[x],dfn[y]);
else{
BCC(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
cnt++;
Tr::push(x,cnt);
do{Tr::push(cnt,stack[Top]);}while(y!=stack[Top--]);
}
}
}
}
void push(int x,int y){e.push2(x,y);}
}
int main(){
int i,x,y; char s[9];
n=ri(),m=ri(),q=ri();
for(i=1;i<=n;i++) val[i]=ri();
for(i=1;i<=m;i++) G::push(ri(),ri());
G::cnt=n;
G::BCC(1,0);
Seg::n=G::cnt;
Tr::split();
for(i=1;i<=n;i++) Tr::mdf(i,0,val[i]);
for(i=1;i<=q;i++){
scanf("%s",s);
if(s[0]=='C'){
x=ri(), y=ri();
Tr::mdf(x,val[x],y);
val[x]=y;
}
else if(s[0]=='A'){
x=ri(),y=ri();
printf("%d
",Tr::get(x,y));
}
}
return 0;
}