CF487E Tourists

发表于

闲扯

这道题也是比较套路的，在之前[APIO2018] Duathlon 铁人两项的基础上，我们可以比较快的找到思路。

题面

CF487E Tourists

Solution

由于是求任意两点间的简单路径的问题，我们考虑建出原图的圆方树。

在铁人两项这道题里面，我们用到了一个结论，根据这个结论，我们可以知道：

当固定 $u,v$ 时，在圆方树上 $u,v$ 的路径上的所有方点周围的圆点我们都能够走到。

我们定义方点的权值为它周围所有圆点的权值的最小值。

那么我们用树剖维护链上所有方点的最小权值即可。

那么修改呢？

如果修改点 $u$ ，我们把所有和它相连的方点都改一遍，很容易卡到 $O(n)$ 。

我们可以利用树的性质，只记录每个方点的子节点中的权值，这样修改就唯一了。

然后查询时，如果最上面是方点，那么还要考虑它的父节点的权值；如果是圆点，那么还要考虑它自己的权值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e5+5;
int n,m,q,u,v,val[MAXN],bl[MAXN],x,y;
char opt[2];
vector<int> G1[MAXN],G2[MAXN<<1];
il add_edge(int u,int v){
	G1[u].push_back(v);
	G1[v].push_back(u);
}
il add(int u,int v){
	G2[u].push_back(v);
	G2[v].push_back(u);
}
int dfn[MAXN],low[MAXN],stk[MAXN],tp,cnt,ver;
multiset<int> s[MAXN<<1];
il Tarjan(int u){
	dfn[u]=low[u]=++cnt,stk[++tp]=u;
	for(ri i=0;i<(int)G1[u].size();++i){
		int v=G1[u][i];
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]==dfn[u]){
				++ver;
				for(ri x=0;x!=v;--tp){
					x=stk[tp];
					add(ver,x);
				}
				add(ver,u);
			}
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
}
int son[MAXN<<1],sz[MAXN<<1],dep[MAXN<<1],top[MAXN<<1],f[MAXN<<1],id[MAXN<<1],rk[MAXN<<1];
il DFS1(int u,int fa){
	f[u]=fa,sz[u]=1,dep[u]=dep[fa]+1;
	for(ri i=0;i<(int)G2[u].size();++i){
		int v=G2[u][i];
		if(v==fa)
			continue;
		if(u>n)
			bl[v]=u,s[u].insert(val[v]);
		DFS1(v,u),sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])
			son[u]=v;
	}
}
il DFS2(int u,int t){
	top[u]=t,id[u]=++cnt,rk[cnt]=u;
	if(!son[u])
		return ;
	DFS2(son[u],t);
	for(ri i=0;i<(int)G2[u].size();++i){
		int v=G2[u][i];
		if(v==f[u]||v==son[u])
			continue;
		DFS2(v,v);
	}
}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
	int mn;
}T[MAXN<<3];
il pushup(int cur){
	T[cur].mn=min(T[lc].mn,T[rc].mn);
}
il Build(int cur,int l,int r){
	if(l==r){
		if(rk[l]<=n)
			T[cur].mn=INF;
		else
			T[cur].mn=*s[rk[l]].begin();
		return ;
	}
	Build(lc,l,mid),Build(rc,mid+1,r);
	pushup(cur);
}
il Updata(int cur,int l,int r,int pos){
	if(l==r){
		T[cur].mn=*s[rk[l]].begin();
		return ;
	}
	if(mid>=pos)
		Updata(lc,l,mid,pos);
	else
		Updata(rc,mid+1,r,pos);
	pushup(cur);
}
it Query(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R)
		return T[cur].mn;
	ri res=INF;
	if(mid>=L)
		res=min(res,Query(lc,l,mid,L,R));
	if(R>mid)
		res=min(res,Query(rc,mid+1,r,L,R));
	return res;
}
it Query_Path(int u,int v){
	if(u==v)
		return val[u];
	ri res=INF;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])
			swap(u,v);
		res=min(res,Query(1,1,ver,id[top[u]],id[u]));
		u=f[top[u]];
	}
	if(dep[u]>dep[v])
		swap(u,v);
	res=min(res,Query(1,1,ver,id[u],id[v]));
	if(u>n)
		res=min(res,val[f[u]]);
	else
		res=min(res,val[u]);
	return res;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(q),ver=n;
	for(ri i=1;i<=n;++i)
		read(val[i]);
	for(ri i=1;i<=m;++i)
		read(u),read(v),add_edge(u,v);
	Tarjan(1),cnt=0;
	DFS1(1,0),DFS2(1,1),Build(1,1,ver);
	for(ri i=1;i<=q;++i){
		scanf("%s",opt);
		read(x),read(y);
		if(opt[0]=='A')
			print(Query_Path(x,y)),puts("");
		if(opt[0]=='C'){
			if(x==1){
				val[x]=y;
				continue;
			}
			s[bl[x]].erase(s[bl[x]].find(val[x]));
			val[x]=y;
			s[bl[x]].insert(val[x]);
			Updata(1,1,ver,id[bl[x]]);
		}
	}
	return 0;
}