Description

ason和ducky两父子一起去旅游。

在那之前，他们要先做一个计划。他们想参观的城市一共有N个，有M条双向道路将这些城市连接在一起。每个城市有自己城市的纪念品，纪念品的价格有时可能会发生变化。为了纪念这次旅行，Jason会在一次旅行中购买途径城市价格最低的纪念品。

现在Jason按照时间顺序告诉你Q个信息或者询问，希望你能帮助他俩完成旅行计划。

Q个信息或询问的格式如下：

C a w :表示a城市的纪念品价格变为w

A a b :表示询问所有以a城市为起点,b城市为终点的旅行路径中途径城市的最低纪念品价格（注意：因为是旅游，所以在一次询问中Jason不希望经过重复的城市）。

Solution

其实就是缩点双，对于每个点双里的点，新建一个方点连向它们，最后构出来的就是圆方树。

考虑没有修改的做法，每个方点权值记为所有连向它的圆点的权值最小值，最后就是链上最小值。

考虑一次修改，复杂度为度数，菊花图会炸。

那么定义方点的权值为它所有儿子原点的权值最小值，修改的时候只用修改父亲方点即可，用set+树剖维护一下。

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define fo(i,j,k) for(int i=j;i<=k;++i)#define fd(i,j,k) for(int i=j;i>=k;--i)#define rep(i,x) for(int i=nw.ls[x];i;i=nw.nx[i])using namespace std;const int N=2e5+10,M=4e5+10;typedef multiset
          
           :: iterator it;multiset
           
             b[N];struct node{ int to[M],nx[M],ls[N],num; void link(int u,int v){ to[++num]=v,nx[num]=ls[u],ls[u]=num; to[++num]=u,nx[num]=ls[v],ls[v]=num; }}nw,ys;int a[N];int dfn[N],low[N],st[N],tot=0,cnt;void tarjan(int x,int fr){ st[dfn[x]=low[x]=++tot]=x; for(int i=ys.ls[x];i;i=ys.nx[i]) if(i!=fr){ int v=ys.to[i]; if(!dfn[v]){ tarjan(v,i^1),low[x]=min(low[x],low[v]); if(low[v]>=dfn[x]){ nw.link(++cnt,x);int xx=0; do{ xx=st[tot--],nw.link(cnt,xx); }while(xx!=v); } } else low[x]=min(low[x],dfn[v]); }}int n;int top[N],son[N],sz[N],L[N],fa[N],dep[N];void pre(int x){ sz[x]=1; rep(i,x){ int v=nw.to[i]; if(v==fa[x]) continue; fa[v]=x,dep[v]=dep[x]+1,pre(v); if(sz[v]>sz[son[x]]) son[x]=v; sz[x]+=sz[v]; } if(x>n) rep(i,x){ int v=nw.to[i]; if(v==fa[x]) continue; b[x].insert(a[v]); }}void pre2(int x,int t){ top[x]=t,L[x]=++tot; if(son[x]) pre2(son[x],t); rep(i,x){ int v=nw.to[i]; if(v==fa[x] || v==son[x]) continue; pre2(v,v); }}int mn[N<<2];int find(int x,int y,int v=1,int l=1,int r=cnt){ if(l==x && r==y) return mn[v]; int mid=(l+r)>>1; if(y<=mid) return find(x,y,v<<1,l,mid); else if(x>mid) return find(x,y,v<<1|1,mid+1,r); else{ int ls=find(x,mid,v<<1,l,mid),rs=find(mid+1,y,v<<1|1,mid+1,r); return min(ls,rs); }}void modify(int x,int p,int v=1,int l=1,int r=cnt){ if(l==r){ mn[v]=p; return; } int mid=(l+r)>>1; x<=mid?modify(x,p,v<<1,l,mid):modify(x,p,v<<1|1,mid+1,r); mn[v]=min(mn[v<<1],mn[v<<1|1]);}int qmin(int u,int v){ int f1=top[u],f2=top[v]; int tmp=1e9; while(f1!=f2){ if(dep[f1]
            
             dep[v]) swap(u,v); tmp=min(tmp,find(L[u],L[v])); if(u>n) tmp=min(tmp,a[fa[u]]); return tmp;}int main(){ int m,q; scanf("%d %d %d",&n,&m,&q); fo(i,1,n) scanf("%d",&a[i]); nw.num=ys.num=1; fo(i,1,m){ int u,v; scanf("%d %d",&u,&v); ys.link(u,v); } cnt=n,tarjan(1,-1); tot=0,pre(1),pre2(1,1); fo(i,1,n) modify(L[i],a[i]); fo(i,n+1,cnt){ it p=b[i].begin(); modify(L[i],*p); } scanf("%d",&q); while(q--){ char op[3]; scanf("%s",op); if(op[0]=='C'){ int x,w,fx; scanf("%d %d",&x,&w),fx=fa[x]; if(fx){ b[fx].erase(b[fx].find(a[x])); b[fx].insert(w); modify(L[fx],*(b[fx].begin())); } a[x]=w,modify(L[x],w); } else{ int u,v; scanf("%d %d",&u,&v); if(u==v){ printf("%d\n",a[u]); continue; } printf("%d\n",qmin(u,v)); } }}