给出一个带点权的无向图，两种操作：
1、修改某点点权。
2、询问x到y之间简单路径能走过的点的最小点权。
题解时间
总感觉是将一堆水题拼出来的丑陋产物(划去)
毫无疑问看题直接搞上圆方树。
用可删堆或者multiset维护方点的权值。
查询直接树剖搞。
但这样会发现修改时间复杂度无法保证。
所以改成每个方点只记录子节点的权值。
当lca为方点时答案计算一下它上面的圆点。
$ O(nlog^{2}n) $
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
typedef long long lint;
template<typename TP>inline void read(TP &tar)
{
TP ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
tar=ret*f;
}
namespace RKK
{
const int N=200011;
struct superheap
{
priority_queue<int> q0,q1;
int size;
int top(){update();return -q0.top();}
void push(int x){q0.push(-x),size++;}
void del(int x){q1.push(-x),size--;}
void update(){while(!q1.empty()){if(q0.top()==q1.top()) q0.pop(),q1.pop();else break;}}
};
int n,nn,m,qaq;
struct segtree
{
int v[N<<2];
void edit(int x,int w,int px=1,int pl=1,int pr=nn)
{
if(pl==pr){v[px]=w;return;}
int pm=pl+pr>>1;
if(x<=pm) edit(x,w,px<<1,pl,pm);
else edit(x,w,px<<1|1,pm+1,pr);
v[px]=min(v[px<<1],v[px<<1|1]);
}
int query(int l,int r,int px=1,int pl=1,int pr=nn)
{
if(l<=pl&&r>=pr) return v[px];
int ret=1145149961;
int pm=pl+pr>>1;
if(l<=pm) ret=min(ret,query(l,r,px<<1,pl,pm));
if(r>pm) ret=min(ret,query(l,r,px<<1|1,pm+1,pr));
return ret;
}
};
struct sumireko{int to,ne;};
int w[N];
int dfn[N],low[N],da;
int sta[N],stp;
int fa[N],dep[N],sz[N],dson[N],top[N],id[N];
superheap heap[N];
segtree sgt;
struct graph
{
sumireko e[N<<1];
int he[N],ecnt;
void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f],he[f]=ecnt;}
void tj(int x,graph *g)
{
dfn[x]=low[x]=++da,sta[++stp]=x;
for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
{
if(!dfn[t])
{
tj(t,g),low[x]=min(low[x],low[t]);
if(low[t]>=dfn[x])
{
nn++;int px=0;
while(px!=t)
{
px=sta[stp--];
g->addline(px,nn),g->addline(nn,px);
}
g->addline(x,nn),g->addline(nn,x);
}
}else low[x]=min(low[x],dfn[t]);
}
}
void dfs(int x)
{
sz[x]=1;
for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(t!=fa[x])
{
fa[t]=x,dep[t]=dep[x]+1,dfs(t),sz[x]+=sz[t];
if(x>n) heap[x].push(w[t]);
if(sz[t]>sz[dson[x]]) dson[x]=t;
}
}
void dfs(int x,int tp)
{
if(x>n) w[x]=heap[x].top();
top[x]=tp,id[x]=++da,sgt.edit(id[x],w[x]);
if(dson[x]) dfs(dson[x],tp);
for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(t!=fa[x]&&t!=dson[x])
dfs(t,t);
}
}g1,g2;
void getans(int x,int y)
{
int ans=1145149961;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=min(ans,sgt.query(id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=min(ans,sgt.query(id[x],id[y]));
if(x>n) ans=min(ans,w[fa[x]]);
printf("%d\n",ans);
}
char op[5];
int Iris()
{
read(n),read(m),read(qaq),nn=n;
for(int i=1;i<=n;i++) read(w[i]);
for(int i=1,x,y;i<=m;i++) read(x),read(y),g1.addline(x,y),g1.addline(y,x);
g1.tj(1,&g2);
g2.dfs(1),da=0,g2.dfs(1,1);
for(int rkk=1,x,y;rkk<=qaq;rkk++)
{
scanf("%s",op),read(x),read(y);
switch(op[0])
{
case 'A':
getans(x,y);
break;
case 'C':
sgt.edit(id[x],y);
if(fa[x])
{
int px=fa[x];
heap[px].del(w[x]);
heap[px].push(y);
if(heap[px].top()!=w[px])
{
sgt.edit(id[px],heap[px].top());
w[px]=heap[px].top();
}
}
w[x]=y;
break;
}
}
return 0;
}
}
int main(){return RKK::Iris();}