求从$ 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 = 0; char zf = 1; char ch = getchar(); while (ch != '-' && !isdigit(ch)) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf; } void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);} void writeln(const ll y){write(y);putchar(' ');} 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+1]!=a[i])s[n].insert(w[sta[top]]),Add(sta[top--],n); Add(x,n); if(!s[n].size())w[n]=999999999;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]=1;fa[x]=pre; for(auto i:e[x])if(i!=pre)deep[i]=deep[x]+1,dfs(i,x),size[x]+=size[i]; } void dfs2(int x,int chain){ dfn[x]=++cnt;to[cnt]=x;int heavy=0;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*4]; 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>>1; build(x<<1,L,mid);build(x<<1|1,mid+1,R); t[x].Min=min(t[x<<1].Min,t[x<<1|1].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>>1; if(R<=mid)return query(x<<1,L,R); if(L>mid)return query(x<<1|1,L,R); return min(query(x<<1,L,R),query(x<<1|1,L,R)); } void change(int x,int val){ x=pl[x];t[x].Min=val;x>>=1; while(x){ t[x].Min=min(t[x<<1].Min,t[x<<1|1].Min); x>>=1; } } int get(int x,int y){ int Min=999999999; while(up[x]!=up[y]){ if(deep[up[x]]<deep[up[y]])swap(x,y); Min=min(Min,query(1,dfn[up[x]],dfn[x])); x=fa[up[x]]; } if(deep[x]<deep[y])swap(x,y); Min=min(Min,query(1,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=1;i<=n;i++)w[i]=read(); for(rt i=1;i<=m;i++){ x=read();y=read(); add(x,y); add(y,x); } tarjan(1);cnt=0; dfs(1,1);dfs2(1,1);build(1,1,n); while(q--){ char c=getopt();x=read();y=read(); if(c=='C'){ if(x!=1){ 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 0; }