【题解】Uoj#30 Tourist(广义圆方树+树上全家桶)
名字听起来很霸气其实算法很简单....
仙人掌上的普通圆方树是普及题，但是广义圆方树虽然很直观但是有很多地方值得深思
说一下算法的流程:
- 对于所有点强连通分量(强联通，意味着要找极大的那个)，建立一个虚点(u)，然后把环内所有边断开，紧接着让环内所有点向这个虚点连边。可以看出对于每一个大小为(s)的SCC，我们导出了一个点数为(s+1)边数为(n)的图且联通，所以圆方树是树。
- 为了方便讨论，对于每个桥加个虚点。虚点维护SCC内所有点的信息
正确性是显然的，因为我如果要从环的某一点a走到另一点b，我一定会在这颗圆方树上经过虚点。虚点可以用不同的方法维护点权信息。
然而不好维护边权，所以我们的做法是直接把边看做一个点建图...
用Tarjan魔改一下就能找了
这一题就是模板题，直接建出来树剖即可。
然后树上的点权修改如果单次修改和度数有关是(O(n))的，一个常见套路是在父亲处打tag，此时为了方便讨论加的规则就派上了用(少讨论很多东西)
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define mid ((l+r)>>1)
#define lef l,mid,pos<<1
#define rgt mid+1,r,pos<<1|1
#define getchar() (__c==__ed?(__ed=__buf+fread(__c=__buf,1,1<<21,stdin),*__c++):*__c++)
using namespace std; typedef long long ll; char __buf[1<<21],*__c=__buf,*__ed=__buf;
inline int qr(){
int ret=0,f=0,c=getchar();
while(!isdigit(c))f|=c==45,c=getchar();
while(isdigit(c)) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=1e5+5;
vector<int> eg[maxn],et[maxn<<1];
int w[maxn<<1];
int dfn[maxn<<1],low[maxn],stk[maxn],top;
int arc[maxn<<1],fi[maxn<<1],d[maxn<<1],r[maxn<<1];
int seg[maxn<<3],siz[maxn<<1],son[maxn<<1];
int n,m,q,cnt;
struct Pri{
multiset<int> s;
int Top;
Pri(){Top=1e9+1;s.clear();}
inline void insert(int x){s.insert(x);Top=*s.begin();}
inline void del(int x){s.erase(s.find(x));Top=*s.begin();}
inline int top(){return Top;}
}p[maxn];
void add(vector<int>*e,int fr,int to){
e[fr].push_back(to);
e[to].push_back(fr);
}
void dfs(int now,int last){
stk[++top]=now; dfn[now]=low[now]=++*dfn;
for(auto t:eg[now]){
if(!dfn[t]){
dfs(t,now);
if(low[t]>=dfn[now]){
++cnt; int temp;
add(et,now,cnt);
do temp=stk[top--],add(et,cnt,temp),p[cnt-n].insert(w[temp]);
while(temp!=t);
}
low[now]=min(low[now],low[t]);
}else low[now]=min(low[now],dfn[t]);
}
}
void build(int l,int r,int pos){
if(l==r) return seg[pos]=w[arc[l]],void();
build(lef); build(rgt);
seg[pos]=min(seg[pos<<1],seg[pos<<1|1]);
}
void upd(int v,int p,int l,int r,int pos){
if(p<l||p>r) return;
if(l==r) return seg[pos]=v,void();
upd(v,p,lef); upd(v,p,rgt);
seg[pos]=min(seg[pos<<1],seg[pos<<1|1]);
}
int que(int L,int R,int l,int r,int pos){
if(L>r||R<l) return 1e9;
if(L<=l&&r<=R) return seg[pos];
return min(que(L,R,lef),que(L,R,rgt));
}
void dfs1(int now,int last){
r[now]=last; d[now]=d[last]+1;
siz[now]=1;
for(auto t:et[now])
if(!siz[t])
dfs1(t,now),siz[now]+=siz[t],son[now]=siz[son[now]]>siz[t]?son[now]:t;
}
void dfs2(int now,int last){
fi[now]=last; dfn[now]=++*dfn; arc[*dfn]=now;
if(son[now]) dfs2(son[now],last);
for(auto t:et[now])
if(!dfn[t]) dfs2(t,t);
}
int que(int u,int v){
int ret=1e9+1;
while(fi[u]^fi[v]){
if(d[fi[u]]<d[fi[v]]) swap(u,v);
ret=min(ret,que(dfn[fi[u]],dfn[u],1,cnt,1));
u=r[fi[u]];
}
if(d[u]<d[v]) swap(u,v);
ret=min(que(dfn[v],dfn[u],1,cnt,1),ret);
if(v>n) ret=min(ret,w[r[v]]);
return ret;
}
int main(){
cnt=n=qr(); m=qr(); q=qr();
for(int t=1;t<=n;++t) w[t]=qr();
for(int t=1,a,b;t<=m;++t)
a=qr(),b=qr(),add(eg,a,b);
for(int t=1;t<=n;++t) if(!dfn[t]) dfs(t,0);
memset(dfn,0,sizeof dfn);
dfs1(1,0); dfs2(1,1);
for(int t=n+1;t<=cnt;++t) w[t]=p[t-n].top();
build(1,cnt,1);
while(q--){
char c=getchar();
while(!isalpha(c)) c=getchar();
int u=qr(),v=qr();
if(c=='A') printf("%d
",que(u,v));
else{
upd(v,dfn[u],1,cnt,1);
if(r[u]){
p[r[u]-n].del(w[u]);
p[r[u]-n].insert(v);
upd(p[r[u]-n].top(),dfn[r[u]],1,cnt,1);
}
w[u]=v;
}
}
return 0;
}