题目描述
求简单无向图两点路径上最小权值，支持修改。
思路
先把图中的点双缩点，维护圆方树，把方点的值设为它儿子中点权最小的点的点权，树链剖分。利用 Multiset 维护每个点双的信息即可。
代码
#include
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 100010
#define mid ((l+r)>>1)
#define ll long long
#define inf INT_MAX
using namespace std;
int n,m,q,val[maxn<<2],pointsum;
multisetst[maxn<<2];
struct ios{
inline char read(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template inline ios & operator >> (_Tp&x){
static char c11,boo;
for(c11=read(),boo=0;!isdigit(c11);c11=read()){
if(c11==-1)return *this;
boo|=c11=='-';
}
for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
boo&&(x=-x);
return *this;
}
}io;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
};
struct Graph{
Edge l[maxn<<2];
int head[maxn<<1],cnt,ind;
int fa[maxn<<1],son[maxn<<1];
int top[maxn<<1],dep[maxn<<1];
int siz[maxn<<1],id[maxn<<1];
int rid[maxn<<1];
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);head[a]=cnt;
l[++cnt]=Edge(a,head[b]);head[b]=cnt;
}
void Pre_Work(int u,int f){
fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
int maxson=-1;
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
Pre_Work(v,u);
siz[u]+=siz[v];
if (siz[v]>maxson)
maxson=siz[v],son[u]=v;
}
}
void Re_Build(int u,int topf){
top[u]=topf;rid[id[u]=++ind]=u;
if (son[u]) Re_Build(son[u],topf);
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==fa[u]||v==son[u]) continue;
Re_Build(v,v);
}
}
int tree[maxn<<4];
void Pushup(int p){
tree[p]=min(tree[ls],tree[rs]);
}
void Build(int l,int r,int p){
if (l==r){tree[p]=val[rid[l]];return;}
Build(l,mid,ls),Build(mid+1,r,rs);
Pushup(p);
}
void Update(int l,int r,int t,int v,int p){
if (l==r){tree[p]=v;return;}
if (t<=mid) Update(l,mid,t,v,ls);
else Update(mid+1,r,t,v,rs);
Pushup(p);
}
int Query(int l,int r,int L,int R,int p){
if (l>R||r=L&&r<=R) return tree[p];
return min(Query(l,mid,L,R,ls),Query(mid+1,r,L,R,rs));
}
int Path_Query(int x,int y){
int res=inf;
while(top[x]!=top[y]){
if (dep[top[x]]dep[y]) swap(x,y);
res=min(res,Query(1,pointsum,id[x],id[y],1));
if (x>n) res=min(res,val[fa[x]]);
return res;
}
}G;
struct DAG{
Edge l[maxn<<1];
int head[maxn],cnt;
int dfn[maxn],low[maxn];
int sta[maxn],ind,top;
void Add(int a,int b){
l[++cnt]=Edge(b,head[a]);
head[a]=cnt;
}
void Tarjan(int u){
low[u]=dfn[u]=++ind;
sta[++top]=u;
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
if (low[v]>=dfn[u]){
int j=-1;pointsum++;
while(j!=v){
j=sta[top--];
G.Add(j,pointsum);
}
G.Add(u,pointsum);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
}D;
int main(){
scanf("%d%d%d",&n,&m,&q);
pointsum=n;
for (int i=1;i<=n;i++) scanf("%d",val+i);
for (int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
D.Add(x,y),D.Add(y,x);
}
for (int i=1;i<=n;i++)
if (!D.dfn[i]) D.Tarjan(i);
G.Pre_Work(1,0),G.Re_Build(1,1);
for (int i=2;i<=n;i++)
st[G.fa[i]-n].insert(val[i]);
for (int i=n+1;i<=pointsum;i++)
val[i]=st[i-n].empty()?inf:*st[i-n].begin();
G.Build(1,pointsum,1);
for (int i=1,x,y;i<=q;i++){
char op[2];
scanf("%s%d%d",op,&x,&y);
if (op[0]=='C'){
G.Update(1,pointsum,G.id[x],y,1);
if (x==1) {val[x]=y;continue;}
int t=G.fa[x];
st[t-n].erase(st[t-n].find(val[x]));
st[t-n].insert(y);
int mt=*st[t-n].begin();
if (mt==val[t]) {val[x]=y;continue;}
G.Update(1,pointsum,G.id[t],mt,1);
val[t]=mt;val[x]=y;
}
if (op[0]=='A'){
printf("%d\n",G.Path_Query(x,y));
}
}
return 0;
}