板子大集合？那我不看题解也没做出来/kk
思路不算难，但是实现起来比较码农
tarjan 建广义圆方树 + 对圆方树树剖 + 用 multiset 维护每个双联通分量最小值
传送门
给出一个图，每个点有一个权值
现在给 (q) 个操作
- 更改一个点的权值
- 查询 (x) 到 (y) 的所有简单路径（不能有重复的点）中，能走到的最小权值是多少
首先，要会用 multiset，还要会tarjan，并且会用他构建广义圆方树，这里
再来看这个题，可以猜出 一个结论：一个点双连通图（分量），对于其中任意三个点 (a,b,c)，一定能找出一条 (a,b) 间的简单路径，使得其穿过 (c)
因为一个点双应该是一个环，然后再加上一堆边组成的，所以找到上面要求的这样一个路径其实很容易，所以就 感性理解 一下就好
比较详细的证明CF官方题解上有
那么，我们只要走到一个点双中，就直接取这个点双的最小值就行了，然后可以继续往前走出去
所以就建一棵圆方树就好了，每个方点维护这个点双中的最小值
对每个方点，还要用一个 multiset（自带排序）来存这个点双的所有点的权值，方便删除和添加新权值来实现更改
对于查询，就直接查这两个点在树上的路径中权值最小值就行了，用树剖维护
考虑怎么修改
发现如果像上面那样维护，每次修改一个圆点权值，都会波及到他周围所有的方点，容易被菊花图卡飞
所以，每个方点的权值应该是：他所有相邻的圆点（就是他所对应的那个点双中的所有点），除了它在圆方树上的父亲，中的点权最小值
这样，修改操作时，每个圆点被修改，都只会波及到它的父亲，就只去更改一下父亲的信息就行了
查询时也要加一个，就是如果 (x,y) 的 LCA 是个方点，那么还要和它的父亲（是个圆点）的权值取 (min)
( exttt{code.}) 写了我一上午/kk
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
#define N 200006
#define M 400006
int n,m;
int w[N];
std::multiset<int>set[N];
struct graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
}
}G,T;
struct get_bcc{
int top,stack[N];
int dfn[N],low[N],dfscnt;
int bcccnt;
void tarjan(int u){
dfn[u]=low[u]=++dfscnt;stack[top++]=u;
for(reg int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(!dfn[v]){
tarjan(v);low[u]=std::min(low[u],low[v]);
if(low[v]>=dfn[u]){
bcccnt++;
do{
T.add(bcccnt,stack[--top]);T.add(stack[top],bcccnt);
}while(stack[top]^v);
T.add(bcccnt,u);T.add(u,bcccnt);
}
}
else low[u]=std::min(low[u],dfn[v]);
}
}
}BCC;
struct TREE{
int fa[N],deep[N],size[N],son[N],index[N];
int top[N],dfn[N],dfscnt;
void dfs1(int u,int fat){
fa[u]=fat;deep[u]=deep[fat]+1;size[u]=1;
for(reg int v,i=T.fir[u];i;i=T.nex[i]){
v=T.to[i];
if(v!=fat){
dfs1(v,u);size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
}
void dfs2(int u,int topnow){
top[u]=topnow;dfn[u]=++dfscnt;index[dfscnt]=u;
if(!son[u]) return;
dfs2(son[u],topnow);
for(reg int v,i=T.fir[u];i;i=T.nex[i]){
v=T.to[i];
if(!dfn[v]) dfs2(v,v);
}
}
struct tr {
tr *ls,*rs;
int min;
}dizhi[N<<1],*root=&dizhi[0];
int tot;
inline void pushup(tr *tree){tree->min=std::min(tree->ls->min,tree->rs->min);}
void build(tr *tree,int l,int r){
if(l==r) return tree->min=w[index[l]],void();
int mid=(l+r)>>1;
tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
build(tree->ls,l,mid);build(tree->rs,mid+1,r);
pushup(tree);
}
void change(tr *tree,int l,int r,int pos,int k){
if(l==r) return tree->min=k,void();
int mid=(l+r)>>1;
if(pos<=mid) change(tree->ls,l,mid,pos,k);
else change(tree->rs,mid+1,r,pos,k);
pushup(tree);
}
int get_min(tr *tree,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tree->min;
int mid=(l+r)>>1;
if(qr<=mid) return get_min(tree->ls,l,mid,ql,qr);
if(ql>mid) return get_min(tree->rs,mid+1,r,ql,qr);
return std::min(get_min(tree->ls,l,mid,ql,qr),get_min(tree->rs,mid+1,r,ql,qr));
}
inline int find(int x,int y){
int ret=0x7f7f7f7f;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) x^=y,y^=x,x^=y;
ret=std::min(ret,get_min(root,1,BCC.bcccnt,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(deep[x]>deep[y]) x^=y,y^=x,x^=y;
ret=std::min(ret,get_min(root,1,BCC.bcccnt,dfn[x],dfn[y]));
if(x>n) ret=std::min(ret,w[fa[x]]);
return ret;
}
}Tree;
int main(){
// std::freopen("tmp.txt","r",stdin);
BCC.bcccnt=n=read();m=read();int q=read();
for(reg int i=1;i<=n;i++) w[i]=read();
for(reg int u,v,i=1;i<=m;i++){
u=read();v=read();
G.add(u,v);G.add(v,u);
}
BCC.tarjan(1);
// std::printf("bcccnt : %d
tot of edges : %d
",BCC.bcccnt,T.tot);
Tree.dfs1(1,0);
Tree.dfs2(1,1);
for(reg int i=2;i<=n;i++) set[Tree.fa[i]-n].insert(w[i]);
//一定从 2 开始循环，因为 1 是跟，用它的父亲（其实他也没有父亲，这里说的是它的 fa 数组），减 n 减成负数，RE
for(reg int i=n+1;i<=BCC.bcccnt;i++)
w[i]=set[i-n].empty()?0x7f7f7f7f:*set[i-n].begin();
Tree.build(Tree.root,1,BCC.bcccnt);
reg int x,y;char op;
while(q--){
std::scanf("%c",&op);
x=read();y=read();
if(op=='C'){
Tree.change(Tree.root,1,BCC.bcccnt,Tree.dfn[x],y);
if(x==1){w[1]=y;continue;}
int ind=Tree.fa[x]-n;
set[ind].erase(set[ind].find(w[x]));
set[ind].insert(y);
int min=*set[ind].begin();
w[x]=y;
if(min!=w[ind+n]) Tree.change(Tree.root,1,BCC.bcccnt,Tree.dfn[ind+n],min);
w[ind+n]=min;
}
else std::printf("%d
",Tree.find(x,y));
}
return 0;
}
```CF487E Tourists