题意：给一张 n n n 点 m m m 边的连通无向图，点帯权， q q q 次操作：
修改一个点的权值。询问两点间所有简单路的最小权值的最小值。n , m , q ≤ 1 0 5 n,m,q\leq 10^5 n,m,q≤105
显然建出圆方树然后询问路径最小值。多半要树链剖分了。
对于方点，其权值为所有相邻的圆点的权值的最小值。
由于圆点权值会修改，所以需要用 multiset 来维护方点权值。
然而圆点可能在多个点双中，修改时不能暴力更新。
所以可以直接根号分治艹过去
分析圆方树的性质，发现方点相邻的圆点只有一个是父结点废话
对每个方点只维护所有儿子的multiset，修改圆点的时候只改父亲，然后询问的时候如果 lca 是方点就手动加上父结点。
这么显然的东西自己就是想不到，好难受啊……
#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <algorithm> #include <set> #define MAXN 200005 #define MAXM 200005 using namespace std; const int INF=2e9; inline int read() { int ans=0; char c=getchar(); while (!isdigit(c)) c=getchar(); while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar(); return ans; } inline char gal() { char c=getchar(); while (!isalpha(c)) c=getchar(); return c; } struct edge{int u,v;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt=1; inline void addnode(int u,int v) { e[++cnt]=(edge){u,v}; nxt[cnt]=head[u]; head[u]=cnt; } int val[MAXN],n,m,q; int dfn[MAXN],low[MAXN],tim; int stk[MAXM],tp,vis[MAXM],bcc[MAXM],vcnt; vector<int> rtt[MAXN]; void tarjan(int u) { dfn[u]=low[u]=++tim; for (int i=head[u];i;i=nxt[i]) { if (!vis[i>>1]&&!bcc[i>>1]) vis[(stk[++tp]=i)>>1]=1; if (!dfn[e[i].v]) { tarjan(e[i].v); low[u]=min(low[u],low[e[i].v]); if (dfn[u]==low[e[i].v]) { rtt[u].push_back(bcc[i>>1]=++vcnt); rtt[bcc[i>>1]].push_back(u); while (vis[i>>1]) { int t=stk[tp--]; vis[t>>1]=0; rtt[bcc[t>>1]=vcnt].push_back(e[t].v); } } } else low[u]=min(low[u],dfn[e[i].v]); } } multiset<int> s[MAXN]; #define e rtt namespace RTT { int dep[MAXN],siz[MAXN],fa[MAXN],son[MAXN]; void dfs(int u) { siz[u]=1; for (int i=0;i<(int)e[u].size();i++) if (!dep[e[u][i]]) { fa[e[u][i]]=u,dep[e[u][i]]=dep[u]+1; dfs(e[u][i]); siz[u]+=siz[e[u][i]]; if (siz[e[u][i]]>siz[son[u]]) son[u]=e[u][i]; } } int dfn[MAXN],lis[MAXN],tp[MAXN],tim; void dfs(int u,int f) { lis[dfn[u]=++tim]=u; if (son[u]) tp[son[u]]=tp[u],dfs(son[u],u); for (int i=0;i<(int)e[u].size();i++) if (e[u][i]!=f&&e[u][i]!=son[u]) dfs(tp[e[u][i]]=e[u][i],u); } #define lc p<<1 #define rc p<<1|1 int mn[MAXN<<2]; inline void update(int p){mn[p]=min(mn[lc],mn[rc]);} void build(int p,int l,int r) { if (l==r) return (void)(mn[p]=(lis[l]<=n? val[lis[l]]:*s[lis[l]].begin())); int mid=(l+r)>>1; build(lc,l,mid),build(rc,mid+1,r); update(p); } void modify(int p,int l,int r,int k) { if (l==r) return (void)(mn[p]=(lis[l]<=n? val[lis[l]]:*s[lis[l]].begin())); int mid=(l+r)>>1; if (k<=mid) modify(lc,l,mid,k); else modify(rc,mid+1,r,k); update(p); } int query(int p,int l,int r,int ql,int qr) { if (ql<=l&&r<=qr) return mn[p]; if (qr<l||r<ql) return INF; int mid=(l+r)>>1; return min(query(lc,l,mid,ql,qr),query(rc,mid+1,r,ql,qr)); } inline void modify(int x,int v) { s[fa[x]].erase(s[fa[x]].find(val[x])); val[x]=v; modify(1,1,vcnt,dfn[x]); s[fa[x]].insert(v); modify(1,1,vcnt,dfn[fa[x]]); } inline int query(int x,int y) { int ans=INF; while (tp[x]!=tp[y]) { if (dep[tp[x]]<dep[tp[y]]) swap(x,y); ans=min(ans,query(1,1,vcnt,dfn[tp[x]],dfn[x])); x=fa[tp[x]]; } if (dep[x]>dep[y]) swap(x,y); if (x>n) ans=min(ans,val[fa[x]]); return min(ans,query(1,1,vcnt,dfn[x],dfn[y])); } } int main() { n=read(),m=read(),q=read(); for (int i=1;i<=n;i++) val[i]=read(); for (int i=1;i<=m;i++) { int u,v; u=read(),v=read(); addnode(u,v),addnode(v,u); } vcnt=n; tarjan(1); for (int u=1;u<=vcnt;u++) { sort(e[u].begin(),e[u].end()); e[u].erase(unique(e[u].begin(),e[u].end()),e[u].end()); } RTT::dep[1]=1,RTT::dfs(1); RTT::tp[1]=1,RTT::dfs(1,0); for (int u=1;u<=n;u++) s[RTT::fa[u]].insert(val[u]); RTT::build(1,1,vcnt); while (q--) { char op=gal(); if (op=='C') { int a,w; a=read(),w=read(); RTT::modify(a,w); } else printf("%d\n",RTT::query(read(),read())); } return 0; }