[CF487E]Tourists

Posted by Dispwnl on May 3, 2019

题目

题目大意

给定一张无向图,每个点有一个权值,求两个点之间所有简单路径上最小值的最小值,要求支持单点修改

Examples

input

3 3 3
1
2
3
1 2
2 3
1 3
A 2 3
C 1 5
A 2 3

output

1
2

input

7 9 4
1
2
3
4
5
6
7
1 2
2 5
1 5
2 3
3 4
2 4
5 6
6 7
5 7
A 2 3
A 6 4
A 6 7
A 3 3

output

2
1
5
3

题解

先建出圆方树来,每个方点维护周围圆点的最小值,这样题目要求的就是两个点树上路径的最小值

但是修改操作不太好搞,会被菊花图卡爆

所以定义方点的值为儿子圆点的最小值,这样如果查询点的$LCA$为方点的话也要和方点父亲比较权值

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<queue>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct Priority{
	priority_queue<int> qu,qu1;
	void push(int x) {qu.push(-x);}
	void del(int x)
	{
		qu1.push(-x);
		while(qu1.top()==qu.top())
		{
			qu1.pop(),qu.pop();
			if(qu1.empty()) break;
		}
	}
	int top() {return qu.empty()?1e9:-qu.top();}
}qu[MAX];
struct p{
	int x,y; 
}c[MAX];
struct q{
	int x;
}s[MAX<<2];
int n,m,num,Q,Top,cnt,tot;
int h[MAX],st[MAX],col[MAX],siz[MAX],son[MAX],dfn[MAX],low[MAX],fa[MAX],a[MAX],id[MAX],re[MAX],top[MAX],d[MAX];
char S[5];
bool use[MAX];
vector<int> vec[MAX];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num,c[++num]=(p){h[y],x},h[y]=num;}
void Add(int x,int y) {vec[x].push_back(y),vec[y].push_back(x);}
void Tarjan(int x,int fa=0)
{
	st[++Top]=x,use[x]=1,low[x]=dfn[x]=++cnt;
	for(int i=h[x],y;i;i=c[i].x)
	  if((y=c[i].y)^fa) if(!dfn[y])
	  {
	  	Tarjan(y,x);
	  	if(low[y]>=dfn[x])
	  	{
	  		Add(++tot,x);
	  		int tt=-1;
	  		while(tt!=y) tt=st[Top--],use[tt]=0,Add(tt,tot);
		}
	  	low[x]=min(low[x],low[y]);
	  }
	  else if(use[x]) low[x]=min(low[x],dfn[y]);
}
void dfs(int x=1,int F=0)
{
	d[x]=d[fa[x]=F]+(siz[x]=1);
	for(int v:vec[x])
	  if(v^F)
	  {
	  	dfs(v,x),siz[x]+=siz[v];
	  	if(x>n) col[v]=x,qu[x].push(a[v]);
	  	if(siz[v]>siz[son[x]]) son[x]=v;
	  }
	if(x>n) a[x]=qu[x].top();
}
void dfs1(int x=1,int tp=1)
{
	top[x]=tp,re[id[x]=++cnt]=x;
	if(!son[x]) return;
	dfs1(son[x],tp);
	for(int v:vec[x])
	  if((v^fa[x])&&(v^son[x])) dfs1(v,v);
}
void pus(int k) {s[k].x=min(s[tl].x,s[tr].x);}
void build(int l=1,int r=tot,int k=1)
{
	if(l==r) return void(s[k].x=a[re[l]]);
	build(l,mid,tl),build(mid+1,r,tr),pus(k);
}
void change(int l,int r,int k,int x,int d)
{
	if(l==r) return void(s[k].x=d);
	if(x<=mid) change(l,mid,tl,x,d);
	else change(mid+1,r,tr,x,d);
	pus(k);
}
int ask(int l,int r,int k,int L,int R)
{
	if(r<L||R<l) return 1e9;
	if(l>=L&&r<=R) return s[k].x;
	return min(ask(l,mid,tl,L,R),ask(mid+1,r,tr,L,R));
}
int ask(int x,int y)
{
	int ans=1e9;
	while(top[x]^top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		ans=min(ans,ask(1,tot,1,id[top[x]],id[x])),x=fa[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	if(x>n) ans=min(ans,a[fa[x]]);
	return min(ans,ask(1,tot,1,id[x],id[y]));
}
int main()
{
	tot=n=read(),m=read(),Q=read();
	for(int i=1;i<=n;++i)
	  a[i]=read();
	for(int i=1;i<=m;++i)
	  add(read(),read());
	for(int i=1;i<=n;++i)
	  if(!dfn[i]) Tarjan(i);
	cnt=0,dfs(),dfs1(),build();
	for(int i=1,A;i<=Q;++i)
	  {
	  	scanf("%s%d",S,&A);
	  	if(S[0]=='C')
	  	{
	  		if(col[A]) qu[col[A]].del(a[A]);
			a[A]=read(),change(1,tot,1,id[A],a[A]);
			if(col[A]) qu[col[A]].push(a[A]),change(1,tot,1,id[col[A]],a[col[A]]=qu[col[A]].top());
		}
	  	else if(S[0]=='A') printf("%d\n",ask(A,read()));
	  }
	return 0;
}