[CF487E]Tourists

题意：一个无向连通图，点有点权，支持单点修改和查询，查询$(x,y)$是找出一条$x$到$y$的简单路径使得路径点权最小值最小，输出这个最小值

码农题...而且细节很多...

先找边双连通分量缩点，对于每个边双，新建一个节点和边双中的每个点连边，不属于任何边双的边就直接连，这样可以建出一棵树，然后就变成树上的问题了，因为进入一个边双就可以遍历它的所有点

对于新建的点，开一个multiset存它儿子的权值，它自己的权值设为multiset的最小值

查询就是路径$\min$，注意如果lca是新建点，那么这个lca的父亲的权值也应该被统计

修改就修改单点，如果父亲是新建点就更新它的multiset还有权值

注意在tarjan时栈中保存的应该是边而不是点

#include<stdio.h>#include<vector>#include<set>using namespace std;const int inf=2147483647;int v[100010],n,m,q,C;struct tree{int h[200010],nex[400010],to[400010],M;multiset<int>s[200010];void ins(int a,int b){M++;to[M]=b;nex[M]=h[a];h[a]=M;}void add(int a,int b){ins(a,b);ins(b,a);}int fa[200010][18],dep[200010];void dfs(int x){dep[x]=dep[fa[x][0]]+1;for(int i=h[x];i;i=nex[i]){if(to[i]!=fa[x][0]){if(x>n)s[x].insert(v[to[i]]);fa[to[i]][0]=x;dfs(to[i]);}}if(x>n)v[x]=*s[x].begin();}int lca(int x,int y){int i;if(dep[x]<dep[y])swap(x,y);for(i=17;i>=0;i--){if(dep[fa[x][i]]>=dep[y])x=fa[x][i];}if(x==y)return x;for(i=17;i>=0;i--){if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];}int siz[200010],son[200010],pos[200010],bl[200010];void dfs1(int x){int i,k=0;siz[x]=1;for(i=h[x];i;i=nex[i]){if(to[i]!=fa[x][0]){dfs1(to[i]);siz[x]+=siz[to[i]];if(siz[to[i]]>siz[k])k=to[i];}}son[x]=k;}void dfs2(int x,int chain){pos[x]=++M;bl[x]=chain;if(son[x])dfs2(son[x],chain);for(int i=h[x];i;i=nex[i]){if(to[i]!=fa[x][0]&&to[i]!=son[x])dfs2(to[i],to[i]);}}int T[800010];void modify(int x,int v){T[x+=M]=v;for(x>>=1;x;x>>=1)T[x]=min(T[x<<1],T[x<<1|1]);}int query(int s,int t){int res=inf;for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){if(~s&1)res=min(res,T[s^1]);if(t&1)res=min(res,T[t^1]);}return res;}void gao(){int i,j;dfs(1);for(j=1;j<18;j++){for(i=1;i<=C;i++)fa[i][j]=fa[fa[i][j-1]][j-1];}dfs1(1);M=0;dfs2(1,1);for(M=1;M<=C+1;M<<=1);for(i=0;i<M;i++)T[i+M]=inf;for(i=1;i<=C;i++)T[pos[i]+M]=v[i];for(i=M-1;i>0;i--)T[i]=min(T[i<<1],T[i<<1|1]);}int querych(int x,int y){int res=inf;while(bl[x]!=bl[y]){if(dep[bl[x]]<dep[bl[y]])swap(x,y);res=min(res,query(pos[bl[x]],pos[x]));x=fa[bl[x]][0];}if(pos[x]>pos[y])swap(x,y);res=min(res,query(pos[x],pos[y]));if(x>n)res=min(res,v[fa[x][0]]);return res;}void modifypt(int x,int d){if(fa[x][0]&&fa[x][0]>n){s[fa[x][0]].erase(s[fa[x][0]].find(v[x]));s[fa[x][0]].insert(d);modify(pos[fa[x][0]],*s[fa[x][0]].begin());}v[x]=d;modify(pos[x],d);}}tr;struct graph{int h[100010],nex[200010],to[200010],M;graph(){M=1;}int fix(int i){return i&1?i^1:i;}void add(int a,int b){M++;to[M]=b;nex[M]=h[a];h[a]=M;}int dfn[100010],low[100010],stk[100010],vis[100010],tp,K;bool ins[200010];vector<int>V;void dfs(int x){int i,j,t,n,m;dfn[x]=low[x]=++M;for(i=h[x];i;i=nex[i]){if(!dfn[to[i]]){ins[stk[++tp]=fix(i)]=1;dfs(to[i]);low[x]=min(low[x],low[to[i]]);if(low[to[i]]>=dfn[x]){K++;V.clear();j=tp;m=0;do{t=stk[j--];m++;if(vis[to[t]]!=K){vis[to[t]]=K;V.push_back(to[t]);}if(vis[to[t^1]]!=K){vis[to[t^1]]=K;V.push_back(to[t^1]);}}while(t!=fix(i));n=V.size();if(m<n)tr.add(x,to[i]);else{C++;for(int x:V)tr.add(x,C);}do{ins[t=stk[tp--]]=0;}while(t!=fix(i));}}else{low[x]=min(low[x],dfn[to[i]]);if(!ins[fix(i)]&&dfn[to[i]]<dfn[x])ins[stk[++tp]=fix(i)]=1;}}}void gao(){int i,x,y;for(i=1;i<=n;i++)scanf("%d",v+i);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}M=0;C=n;dfs(1);}}g;int main(){char s[5];int x,y;scanf("%d%d%d",&n,&m,&q);g.gao();tr.gao();while(q--){scanf("%s%d%d",s,&x,&y);if(s[0]=='C')tr.modifypt(x,y);elseprintf("%d\n",tr.querych(x,y));}}