题目
题目大意
给定一张无向图，每个点有一个权值，求两个点之间所有简单路径上最小值的最小值，要求支持单点修改
Examples
input
3 3 3
1
2
3
1 2
2 3
1 3
A 2 3
C 1 5
A 2 3
output
1
2
input
7 9 4
1
2
3
4
5
6
7
1 2
2 5
1 5
2 3
3 4
2 4
5 6
6 7
5 7
A 2 3
A 6 4
A 6 7
A 3 3
output
2
1
5
3
题解
先建出圆方树来，每个方点维护周围圆点的最小值，这样题目要求的就是两个点树上路径的最小值
但是修改操作不太好搞，会被菊花图卡爆
所以定义方点的值为儿子圆点的最小值，这样如果查询点的$LCA$为方点的话也要和方点父亲比较权值
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<queue>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct Priority{
priority_queue<int> qu,qu1;
void push(int x) {qu.push(-x);}
void del(int x)
{
qu1.push(-x);
while(qu1.top()==qu.top())
{
qu1.pop(),qu.pop();
if(qu1.empty()) break;
}
}
int top() {return qu.empty()?1e9:-qu.top();}
}qu[MAX];
struct p{
int x,y;
}c[MAX];
struct q{
int x;
}s[MAX<<2];
int n,m,num,Q,Top,cnt,tot;
int h[MAX],st[MAX],col[MAX],siz[MAX],son[MAX],dfn[MAX],low[MAX],fa[MAX],a[MAX],id[MAX],re[MAX],top[MAX],d[MAX];
char S[5];
bool use[MAX];
vector<int> vec[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num,c[++num]=(p){h[y],x},h[y]=num;}
void Add(int x,int y) {vec[x].push_back(y),vec[y].push_back(x);}
void Tarjan(int x,int fa=0)
{
st[++Top]=x,use[x]=1,low[x]=dfn[x]=++cnt;
for(int i=h[x],y;i;i=c[i].x)
if((y=c[i].y)^fa) if(!dfn[y])
{
Tarjan(y,x);
if(low[y]>=dfn[x])
{
Add(++tot,x);
int tt=-1;
while(tt!=y) tt=st[Top--],use[tt]=0,Add(tt,tot);
}
low[x]=min(low[x],low[y]);
}
else if(use[x]) low[x]=min(low[x],dfn[y]);
}
void dfs(int x=1,int F=0)
{
d[x]=d[fa[x]=F]+(siz[x]=1);
for(int v:vec[x])
if(v^F)
{
dfs(v,x),siz[x]+=siz[v];
if(x>n) col[v]=x,qu[x].push(a[v]);
if(siz[v]>siz[son[x]]) son[x]=v;
}
if(x>n) a[x]=qu[x].top();
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,re[id[x]=++cnt]=x;
if(!son[x]) return;
dfs1(son[x],tp);
for(int v:vec[x])
if((v^fa[x])&&(v^son[x])) dfs1(v,v);
}
void pus(int k) {s[k].x=min(s[tl].x,s[tr].x);}
void build(int l=1,int r=tot,int k=1)
{
if(l==r) return void(s[k].x=a[re[l]]);
build(l,mid,tl),build(mid+1,r,tr),pus(k);
}
void change(int l,int r,int k,int x,int d)
{
if(l==r) return void(s[k].x=d);
if(x<=mid) change(l,mid,tl,x,d);
else change(mid+1,r,tr,x,d);
pus(k);
}
int ask(int l,int r,int k,int L,int R)
{
if(r<L||R<l) return 1e9;
if(l>=L&&r<=R) return s[k].x;
return min(ask(l,mid,tl,L,R),ask(mid+1,r,tr,L,R));
}
int ask(int x,int y)
{
int ans=1e9;
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=min(ans,ask(1,tot,1,id[top[x]],id[x])),x=fa[top[x]];
}
if(d[x]>d[y]) swap(x,y);
if(x>n) ans=min(ans,a[fa[x]]);
return min(ans,ask(1,tot,1,id[x],id[y]));
}
int main()
{
tot=n=read(),m=read(),Q=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=m;++i)
add(read(),read());
for(int i=1;i<=n;++i)
if(!dfn[i]) Tarjan(i);
cnt=0,dfs(),dfs1(),build();
for(int i=1,A;i<=Q;++i)
{
scanf("%s%d",S,&A);
if(S[0]=='C')
{
if(col[A]) qu[col[A]].del(a[A]);
a[A]=read(),change(1,tot,1,id[A],a[A]);
if(col[A]) qu[col[A]].push(a[A]),change(1,tot,1,id[col[A]],a[col[A]]=qu[col[A]].top());
}
else if(S[0]=='A') printf("%d\n",ask(A,read()));
}
return 0;
}
