求从$ x$走到$ y$的路径上可能经过的最小点权，带修改 UOJ #30
$ Solution：$
如果两个点经过了某个连通分量，一定可以走到这个连通分量的最小值
直接构建圆方树，圆点存原点的点权，方点用$ multiset$存连通分量的点权集合，权值为集合中的最小值
每次询问就变成求圆方树中一条树链的最小值，可以用树链剖分维护
考虑修改一个圆点的点权
对于这个圆点直接修改，但如果暴力修改周围方点，复杂度明显爆炸
我们修改一下方点的定义，改为这个连通分量中除了自己父亲圆点外其他圆点的最小权值
这样修改一个圆点的权值的时候只需要这个圆点的父亲方点的权值
每次询问的时候如果$ LCA$为方点还要额外考虑这个方点的父亲圆点的贡献
这样就可以在$ O(n log^2 n)$的时间复杂度内解决这个问题
$ my \ code:$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define M 200010
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x = ; char zf = ; char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (isdigit(ch)) x = x * + ch - '', ch = getchar(); return x * zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt;
int F[M],L[M],N[M],a[M],c[M],dfn[M],low[M],w[M],v[M];
void add(int x,int y){
a[++k]=y;
if(!F[x])F[x]=k;
else N[L[x]]=k;
L[x]=k;
}
int sta[M],top;
vector<int>e[M];
multiset<int>s[M];
void Add(int x,int y){
e[x].push_back(y);
e[y].push_back(x);
}
void tarjan(int x){
dfn[x]=low[x]=++cnt;sta[++top]=x;
for(rt i=F[x];i;i=N[i]){
if(!dfn[a[i]]){
tarjan(a[i]),low[x]=min(low[x],low[a[i]]);
if(low[a[i]]>=dfn[x]){
n++;
while(sta[top+]!=a[i])s[n].insert(w[sta[top]]),Add(sta[top--],n);
Add(x,n);
if(!s[n].size())w[n]=;else w[n]=*s[n].begin();
}
}
low[x]=min(low[x],dfn[a[i]]);
}
}
char getopt(){
char c=getchar();
while(c!='A'&&c!='C')c=getchar();
return c;
}
int size[M],deep[M],fa[M],to[M],up[M],pl[M],NN;
void dfs(int x,int pre){
size[x]=;fa[x]=pre;
for(auto i:e[x])if(i!=pre)deep[i]=deep[x]+,dfs(i,x),size[x]+=size[i];
}
void dfs2(int x,int chain){
dfn[x]=++cnt;to[cnt]=x;int heavy=;up[x]=chain;
for(auto i:e[x])if(i!=fa[x])if(size[i]>size[heavy])heavy=i;
if(!heavy)return;
dfs2(heavy,chain);
for(auto i:e[x])if(i!=heavy&&i!=fa[x])dfs2(i,i);
}
struct seg{
int L,R,Min;
}t[M*];
void build(int x,int L,int R){
t[x].L=L;t[x].R=R;
if(L==R)return t[x].Min=w[to[L]],pl[to[L]]=x,void();
const int mid=L+R>>;
build(x<<,L,mid);build(x<<|,mid+,R);
t[x].Min=min(t[x<<].Min,t[x<<|].Min);
}
inline int min(const int &x,const int &y){
return x<y?x:y;
}
int query(int x,int L,int R){
if(t[x].L>=L&&t[x].R<=R)return t[x].Min;
const int mid=t[x].L+t[x].R>>;
if(R<=mid)return query(x<<,L,R);
if(L>mid)return query(x<<|,L,R);
return min(query(x<<,L,R),query(x<<|,L,R));
}
void change(int x,int val){
x=pl[x];t[x].Min=val;x>>=;
while(x){
t[x].Min=min(t[x<<].Min,t[x<<|].Min);
x>>=;
}
}
int get(int x,int y){
int Min=;
while(up[x]!=up[y]){
if(deep[up[x]]<deep[up[y]])swap(x,y);
Min=min(Min,query(,dfn[up[x]],dfn[x]));
x=fa[up[x]];
}
if(deep[x]<deep[y])swap(x,y);
Min=min(Min,query(,dfn[y],dfn[x]));
if(y>NN)Min=min(Min,w[fa[y]]);
return Min;
}
int main(){
n=NN=read();m=read();int q=read();
for(rt i=;i<=n;i++)w[i]=read();
for(rt i=;i<=m;i++){
x=read();y=read();
add(x,y);
add(y,x);
}
tarjan();cnt=;
dfs(,);dfs2(,);build(,,n);
while(q--){
char c=getopt();x=read();y=read();
if(c=='C'){
if(x!=){
s[fa[x]].erase(s[fa[x]].find(w[x]));
s[fa[x]].insert(y);
int v=*s[fa[x]].begin();
if(v!=w[fa[x]]){
w[fa[x]]=v;
change(fa[x],v);
}
}
w[x]=y;
change(x,y);
continue;
}
writeln(get(x,y));
}
return ;
}