【题解】Uoj#30 Tourist(广义圆方树+树上全家桶)

名字听起来很霸气其实算法很简单....

仙人掌上的普通圆方树是普及题，但是广义圆方树虽然很直观但是有很多地方值得深思

说一下算法的流程:

对于所有点强连通分量(强联通，意味着要找极大的那个)，建立一个虚点\(u\)，然后把环内所有边断开，紧接着让环内所有点向这个虚点连边。可以看出对于每一个大小为\(s\)的SCC，我们导出了一个点数为\(s+1\)边数为\(n\)的图且联通，所以圆方树是树。
为了方便讨论，对于每个桥加个虚点。虚点维护SCC内所有点的信息

正确性是显然的，因为我如果要从环的某一点a走到另一点b，我一定会在这颗圆方树上经过虚点。虚点可以用不同的方法维护点权信息。

然而不好维护边权，所以我们的做法是直接把边看做一个点建图...

用Tarjan魔改一下就能找了

这一题就是模板题，直接建出来树剖即可。

然后树上的点权修改如果单次修改和度数有关是\(O(n)\)的，一个常见套路是在父亲处打tag，此时为了方便讨论加的规则就派上了用(少讨论很多东西)

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<set>

#define mid ((l+r)>>1)

#define lef l,mid,pos<<1

#define rgt mid+1,r,pos<<1|1

#define getchar() (__c==__ed?(__ed=__buf+fread(__c=__buf,1,1<<21,stdin),*__c++):*__c++)

using namespace std;  typedef long long ll;   char __buf[1<<21],*__c=__buf,*__ed=__buf;

inline int qr(){

	int ret=0,f=0,c=getchar();

	while(!isdigit(c))f|=c==45,c=getchar();

	while(isdigit(c)) ret=ret*10+c-48,c=getchar();

	return f?-ret:ret;

}

const int maxn=1e5+5;

vector<int> eg[maxn],et[maxn<<1];

int w[maxn<<1];

int dfn[maxn<<1],low[maxn],stk[maxn],top;

int arc[maxn<<1],fi[maxn<<1],d[maxn<<1],r[maxn<<1];

int seg[maxn<<3],siz[maxn<<1],son[maxn<<1];

int n,m,q,cnt;

struct Pri{

	multiset<int> s;

	int Top;

	Pri(){Top=1e9+1;s.clear();}

	inline void insert(int x){s.insert(x);Top=*s.begin();}

	inline void del(int x){s.erase(s.find(x));Top=*s.begin();}

	inline int top(){return Top;}

}p[maxn];

void add(vector<int>*e,int fr,int to){

	e[fr].push_back(to);

	e[to].push_back(fr);

}

void dfs(int now,int last){

	stk[++top]=now; dfn[now]=low[now]=++*dfn;

	for(auto t:eg[now]){

		if(!dfn[t]){

			dfs(t,now);

			if(low[t]>=dfn[now]){

				++cnt; int temp;

				add(et,now,cnt);

				do temp=stk[top--],add(et,cnt,temp),p[cnt-n].insert(w[temp]);

				while(temp!=t);

			}

			low[now]=min(low[now],low[t]);

		}else low[now]=min(low[now],dfn[t]);

	}

}

void build(int l,int r,int pos){

	if(l==r) return seg[pos]=w[arc[l]],void();

	build(lef); build(rgt);

	seg[pos]=min(seg[pos<<1],seg[pos<<1|1]);

}

void upd(int v,int p,int l,int r,int pos){

	if(p<l||p>r) return;

	if(l==r) return seg[pos]=v,void();

	upd(v,p,lef); upd(v,p,rgt);

	seg[pos]=min(seg[pos<<1],seg[pos<<1|1]);

}

int que(int L,int R,int l,int r,int pos){

	if(L>r||R<l) return 1e9;

	if(L<=l&&r<=R) return seg[pos];

	return min(que(L,R,lef),que(L,R,rgt));

}

void dfs1(int now,int last){

	r[now]=last; d[now]=d[last]+1;

	siz[now]=1;

	for(auto t:et[now])

		if(!siz[t])

			dfs1(t,now),siz[now]+=siz[t],son[now]=siz[son[now]]>siz[t]?son[now]:t;

}

void dfs2(int now,int last){

	fi[now]=last; dfn[now]=++*dfn; arc[*dfn]=now;

	if(son[now]) dfs2(son[now],last);

	for(auto t:et[now])

		if(!dfn[t]) dfs2(t,t);

}

int que(int u,int v){

	int ret=1e9+1;

	while(fi[u]^fi[v]){

		if(d[fi[u]]<d[fi[v]]) swap(u,v);

		ret=min(ret,que(dfn[fi[u]],dfn[u],1,cnt,1));

		u=r[fi[u]];

	}

	if(d[u]<d[v]) swap(u,v);

	ret=min(que(dfn[v],dfn[u],1,cnt,1),ret);

	if(v>n) ret=min(ret,w[r[v]]);

	return ret;

}

int main(){

	cnt=n=qr(); m=qr(); q=qr();

	for(int t=1;t<=n;++t) w[t]=qr();

	for(int t=1,a,b;t<=m;++t)

		a=qr(),b=qr(),add(eg,a,b);

	for(int t=1;t<=n;++t) if(!dfn[t]) dfs(t,0);

	memset(dfn,0,sizeof dfn);

	dfs1(1,0); dfs2(1,1);

	for(int t=n+1;t<=cnt;++t) w[t]=p[t-n].top();

	build(1,cnt,1);

	while(q--){

		char c=getchar();

		while(!isalpha(c)) c=getchar();

		int u=qr(),v=qr();

		if(c=='A') printf("%d\n",que(u,v));

		else{

			upd(v,dfn[u],1,cnt,1);

			if(r[u]){

				p[r[u]-n].del(w[u]);

				p[r[u]-n].insert(v);

				upd(p[r[u]-n].top(),dfn[r[u]],1,cnt,1);

			}

			w[u]=v;

		}

	}

	return 0;

}

巴特西

【题解】Uoj#30 Tourist(广义圆方树+树上全家桶)

【题解】Uoj#30 Tourist(广义圆方树+树上全家桶)

最新文章

热门文章