There are n cities in Cyberland, numbered from 1 to n, connected by m bidirectional roads. The j-th road connects city aj and bj.
For tourists, souvenirs are sold in every city of Cyberland. In particular, city i sell it at a PRice of wi.
Now there are q queries for you to handle. There are two types of queries:
"C a w": The price in city a is changed to w."A a b": Now a tourist will travel from city a to b. He will choose a route, he also doesn't want to visit a city twice. He will buy souvenirs at the city where the souvenirs are the cheapest (possibly exactly at city a or b). You should output the minimum possible price that he can buy the souvenirs during his travel.More formally, we can define routes as follow:
A route is a sequence of cities [x1, x2, ..., xk], where k is a certain positive integer.For any 1 ≤ i < j ≤ k, xi ≠ xj.For any 1 ≤ i < k, there is a road connecting xi and xi + 1.The minimum price of the route is min(wx1, wx2, ..., wxk).The required answer is the minimum value of the minimum prices of all valid routes from a to b.InputThe first line of input contains three integers n, m, q (1 ≤ n, m, q ≤ 105), separated by a single space.
Next n lines contain integers wi (1 ≤ wi ≤ 109).
Next m lines contain pairs of space-separated integers aj and bj (1 ≤ aj, bj ≤ n, aj ≠ bj).
It is guaranteed that there is at most one road connecting the same pair of cities. There is always at least one valid route between any two cities.
Next q lines each describe a query. The format is "C a w" or "A a b" (1 ≤ a, b ≤ n, 1 ≤ w ≤ 109).
OutputFor each query of type "A", output the corresponding answer.
Examplesinput3 3 31231 22 31 3A 2 3C 1 5A 2 3output12input7 9 412345671 22 51 52 33 42 45 66 75 7A 2 3A 6 4A 6 7A 3 3output2153NoteFor the second sample, an optimal routes are:
From 2 to 3 it is [2, 3].
From 6 to 4 it is [6, 5, 1, 2, 4].
From 6 to 7 it is [6, 5, 7].
From 3 to 3 it is [3].
题目大意：给出一个无向简单图，保证任意顶点之间是连通的。每个点有一个点权。
操作分为两种，一种是更改点的点权；另一种是给出起点和终点，求从起点到终点的路径中可能经过的最小点权。
题解：树链剖分+tarjan
给出点双连通分量的定义：对于一个连通图，如果任意两点至少存在两条点不重复路径，则称这个图为点双连通的（简称双连通）。那么同属一个点双连通分量的点，到达其中的一个点就一定能到达连通分量中的所有点。但是我们无法直接进行缩点，因为有些割点会属于很多的点双连通图分量。所以我们对于每个点双连通分量新建一个节点，将所有属于他的点都与他连边，然后我们会得到一颗树。这颗树有不错的性质，首先一定是原图的点与新建节点交替分布的(即不会存在两个原图的点直接相连)。所有非叶子节点的原图的点对应的都是原图的割点。这样我们就得到了一棵树，是所有的点都与他所属的点双相连，并且没有冲突。
那么我们就可以在这棵树上搞事情了。
对于点双的权值，我们定义为他所有儿子节点中的最小点权，这个需要用multiset来维护。
修改一个点的点权也需要对应的修改，他所属的点双(父节点)。
对于查询，因为我们只要经过点双中的一个点就可以获取点双中的最小权值。所以我们对树进行树链剖分，然后查询路径上的最小值即可。需要注意的是如果两个点的lca是新建的点双节点那么我们还要加入fa[lca]的权值，fa[lca]也是属于lca这点双的，只不过是我们没有维护进去。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<set>#define N 500003#define inf 1000000000using namespace std;int n,m,q,tot,cnt,sz,top,root,n1;int belong[N],st[N],low[N],dfsn[N],bl[N],head[N],nxt[N],next[N],point[N],val[N];int u[N],v[N],ins[N],vis[N],mark[N],tr[N*4],pos[N],p[N],fa[N],deep[N],size[N],son[N];int bk[N];multiset<int> c[N];void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; u[tot]=y; tot++; next[tot]=head[y]; head[y]=tot; u[tot]=x;}void addedge(int x,int y){ tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;}void tarjan(int x){ st[++top]=x; low[x]=dfsn[x]=++sz; ins[x]=1; for (int i=head[x];i;i=next[i]) { int j=u[i]; if (!dfsn[j]) { tarjan(j); low[x]=min(low[x],low[j]); if (dfsn[x]<=low[j]) { ++cnt; mark[x]=1; int k; while (1){ k=st[top--]; bl[k]=cnt; addedge(cnt+n,k); if (k==j) break; } addedge(cnt+n,x); root=x; } } else if (ins[j]) low[x]=min(low[x],dfsn[j]); }}void search(int x){ addedge(cnt+n,x); vis[x]=cnt; bl[x]=cnt; for (int i=head[x];i;i=next[i]) { if (mark[u[i]]&&vis[u[i]]!=cnt) { vis[u[i]]=cnt; addedge(cnt+n,u[i]); continue; } if (vis[u[i]]) continue; search(u[i]); }}void dfs(int x,int f){ fa[x]=f; size[x]=1; deep[x]=deep[f]+1; for (int i=point[x];i;i=nxt[i]) { if (v[i]==f) continue; dfs(v[i],x); size[x]+=size[v[i]]; if (size[son[x]]<size[v[i]]) son[x]=v[i]; }}void dfs1(int x,int chain){ belong[x]=chain; pos[x]=++sz; p[sz]=x; if (!son[x]) return; dfs1(son[x],chain); for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa[x]&&v[i]!=son[x]) dfs1(v[i],v[i]);}void update(int now){ tr[now]=min(tr[now<<1],tr[now<<1|1]);}void build(int now,int l,int r){ if (l==r) { tr[now]=val[p[l]]; return; } int mid=(l+r)/2; build(now<<1,l,mid); build(now<<1|1,mid+1,r); update(now);}void pointchange(int now,int l,int r,int x,int v){ if (l==r) { tr[now]=v; return; } int mid=(l+r)/2; if (x<=mid) pointchange(now<<1,l,mid,x,v); else pointchange(now<<1|1,mid+1,r,x,v); update(now);}int find(int now,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[now]; int mid=(l+r)/2; int ans=inf; if (ll<=mid) ans=min(ans,find(now<<1,l,mid,ll,rr)); if (rr>mid) ans=min(ans,find(now<<1|1,mid+1,r,ll,rr)); return ans;}int solve(int x,int y){ int ans=inf; while (belong[x]!=belong[y]) { if (deep[belong[x]]<deep[belong[y]]) swap(x,y); ans=min(ans,find(1,1,n,pos[belong[x]],pos[x])); x=fa[belong[x]]; } if (deep[x]>deep[y]) swap(x,y); ans=min(ans,find(1,1,n,pos[x],pos[y])); if (x>n1&&fa[x]) ans=min(ans,find(1,1,n,pos[fa[x]],pos[fa[x]])); return ans;}int main(){ freopen("tourists.in","r",stdin); freopen("tourists.out","w",stdout); scanf("%d%d%d",&n,&m,&q); for (int i=1;i<=n;i++) scanf("%d",&val[i]); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); } for (int i=1;i<=2*n;i++) bk[i]=i; tot=0; for (int i=1;i<=n;i++) if (!dfsn[i]) tarjan(i); if (cnt==1) root=cnt+n; dfs(root,0); sz=0; dfs1(root,root); for (int i=n+1;i<=n+cnt;i++) val[i]=inf; for (int i=1;i<=n;i++) { if (i==root) continue; bl[i]=fa[i]; int t=bl[i]; c[t].insert(val[i]); val[t]=min(val[t],*c[t].begin()); } n1=n; n+=cnt; build(1,1,n); for (int i=1;i<=q;i++) { char opt[10]; int x,y; scanf("%s%d%d",opt,&x,&y); if (opt[0]=='A') { printf("%d/n",solve(x,y)); } else { pointchange(1,1,n,pos[x],y); if (x==root) { val[x]=y; continue; } int t=bl[x]; c[t].erase(c[t].find(val[x])); val[x]=y; c[t].insert(val[x]); val[t]=*c[t].begin(); pointchange(1,1,n,pos[t],val[t]); } }}
新闻热点
疑难解答
