园方树+树链剖分
这题首先容易得到的性质是，一个点双内的所有点互相到达，这就说明这个点双的答案就是他们中的最小值，因此建立园方树。方点就维护了最值
现在有修改问题，对于一个圆点的修改，势必要影响到方点，我们对每个方点维护一个multiset，这样对于每个圆点的修改，都是对他的父亲方点进行修改，这样可以维护单点权值
那么查询的时候，因为是一段路径，因此考虑树链剖分后查询，唯一有一个特殊点就是，当他们的lca是方点，那么这个方点的父亲圆点信息也可能影响方案，这里注意一下即可。
这道题算法比较明显，就是模板多。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+10; const int mod=1e9+7; const int inf=0x3f3f3f3f; int h[N],e[N],ne[N],idx; int dfn[N],ins[N],low[N],w[N],times; int depth[N],fa[N],id[N],top[N],son[N],sz[N]; stack<int> st; vector<int> g[N]; multiset<int> m1[N]; int vis[N]; int cnt; int n,m; struct node{ int l,r; ll mi; }tr[N<<2]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u){ ins[u]=1; dfn[u]=low[u]=++times; int i; st.push(u); for(int i=h[u];i!=-1;i=ne[i]){ int v=e[i]; if(!dfn[v]){ fa[v]=u; tarjan(v); low[u]=min(low[u], low[v]); if(dfn[u]<=low[v]){ ++cnt; while(1){ auto x=st.top(); g[cnt].push_back(x); g[x].push_back(cnt); ins[x]=0; st.pop(); if(x==v) break; } g[cnt].push_back(u); g[u].push_back(cnt); } } else if(v!=fa[u]){ low[u]=min(low[u], dfn[v]); } } } void dfs1(int u,int ff){ int i; sz[u]=1; vis[u]=1; for(i=0;i<(int)g[u].size();i++){ int j=g[u][i]; if(vis[j]) continue; depth[j]=depth[u]+1; fa[j]=u; dfs1(j,u); sz[u]+=sz[j]; if(sz[j]>sz[son[u]]){ son[u]=j; } } } void dfs2(int u,int x){ vis[u]=1; top[u]=x; dfn[u]=++times; id[times]=u; if(!son[u]) return ; dfs2(son[u],x); int i; for(i=0;i<(int)g[u].size();i++){ int j=g[u][i]; if(vis[j]) continue; dfs2(j,j); } } void pushup(int u){ tr[u].mi=min(tr[u<<1].mi,tr[u<<1|1].mi); } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,w[id[l]]}; } else{ tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } void modify(int u,int l,int x){ if(tr[u].l==tr[u].r){ tr[u].mi=x; return ; } int mid=tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,x); else modify(u<<1|1,l,x); pushup(u); } int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r){ return tr[u].mi; } int mid=tr[u].r+tr[u].l>>1; int res=inf; if(l<=mid) res=query(u<<1,l,r); if(r>mid) res=min(res,query(u<<1|1,l,r)); return res; } int pathquery(int x,int y){ int res=inf; while(top[x]!=top[y]){ if(depth[top[x]]<depth[top[y]]) swap(x,y); res=min(res,query(1,dfn[top[x]],dfn[x])); x=fa[top[x]]; } if(depth[x]>depth[y]) swap(x,y); res=min(res,query(1,dfn[x],dfn[y])); if(x>n){ res=min(res,w[fa[x]]); } return res; } int main(){ ios::sync_with_stdio(false); int i,j,q; cin>>n>>m>>q; memset(h,-1,sizeof h); cnt=n; for(i=1;i<=n;i++) cin>>w[i]; for(i=1;i<=m;i++){ int a,b; cin>>a>>b; add(a,b); add(b,a); } tarjan(1); times=0; depth[1]=1; dfs1(1,0); memset(vis,0,sizeof vis); dfs2(1,1); for(i=2;i<=n;i++){ m1[fa[i]-n].insert(w[i]); } for(i=n+1;i<=cnt;i++){ w[i]=(m1[i-n].empty())?inf:*m1[i-n].begin(); } build(1,1,cnt); while(q--){ string opt; cin>>opt; if(opt=="C"){ int x,tmp; cin>>x>>tmp; modify(1,dfn[x],tmp); if(x==1){ w[x]=tmp; continue; } m1[fa[x]-n].erase(m1[fa[x]-n].lower_bound(w[x])); m1[fa[x]-n].insert(tmp); w[x]=tmp; if(*m1[fa[x]-n].begin()==w[fa[x]]){ continue; } int pos=*m1[fa[x]-n].begin(); w[fa[x]]=pos; modify(1,dfn[fa[x]],pos); } else{ int a,b; cin>>a>>b; cout<<pathquery(a,b)<<endl; } } }