cf 487E Tourist

题目大意

给定\(n\)个点\(m\)条边的无向连通图，无重边

每个点有点权

两个操作：

1.单点点权修改

2.询问从x到y的简单路径中，路径经过点的最小值的最小值时多少

（简单路径指经过每一个点至多一次）

分析

使用点双连通分量转化为树

（点双连通分量表示该连通分量中，去掉任意一个点都不回使其不连通）

这样子

当我们经过一个点双连通分量的至少两个点时，可以拿到这个点双内的最小权值

证明：

1.当只经过一个点时，经过的是一个割点，只经过一个点的情况下，不能进入该点双

2.当经过至少两个点时

①该点双只有两个点，显然成立

②该点双有\(\ge 3\)个点时，设最开始经过a，最后经过的点是b，该点双的最小值为c

当c为a或者b时，成立

否则，一定存在一条从a-c-b的路径

证明：

因为是点双，所以a-c,a-b,c-b的路径一定都是存在的

假设不存在从a-c-b的路径

说明任选一个a-c路径，所有b-c路径都与它有交

若交点有两个，则可以从a出发，走最近的交点到c，然后走另一个交点去b

否则只有一个交点，该点为b-c的必经点，删除后导致点双不连通，与定义矛盾

做法

类似圆方树的方法

点双中间加个特殊点

这篇博客挺好的

修改时不能全改（儿子多）

那就只改父亲

特判lca为特殊的情况，此时经过了该点双至少两个点

而点双中特殊点的父亲那个点并没有统计到

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <functional>

#include <algorithm>

#include <queue>

using namespace std;

const int M=2e5+7;

const int INF=1e9+7;

inline int ri(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int n,m,q;

int val[M];

struct vec{

	int g[M],te;

	struct edge{

		int y,nxt;

		edge(int _y=0,int _nxt=0){y=_y,nxt=_nxt;}

	}e[M<<1];

	vec(){memset(g,0,sizeof g);te=0;}

	inline void push(int x,int y){e[++te]=edge(y,g[x]);g[x]=te;}

	inline void push2(int x,int y){push(x,y);push(y,x);}

	inline int& operator () (int x){return g[x];}

	inline edge& operator [] (int x){return e[x];}

}e;

struct Heap{

	priority_queue<int,vector<int>,greater<int> >q,ers;

	inline void ins(int d){q.push(d);}

	inline void del(int d){ers.push(d);}

	int top(){

		while(!ers.empty()&&q.top()==ers.top()) q.pop(),ers.pop();

		return q.top();

	}

};

namespace Seg{

	int a[524299];

	int n;

	inline void pushup(int x){a[x]=min(a[x<<1],a[x<<1|1]);}

	void ins(int x,int l,int r,int to,int d){

		if(l==r){

			a[x]=d;

			return;

		}

		int mid=l+r>>1;

		if(to<=mid) ins(x<<1,l,mid,to,d);

		else ins(x<<1|1,mid+1,r,to,d);

		pushup(x);

	}

	int get(int x,int l,int r,int tl,int tr){

		if(tl<=l&&r<=tr) return a[x];

		int mid=l+r>>1;

		if(tr<=mid) return get(x<<1,l,mid,tl,tr);

		if(mid<tl) return get(x<<1|1,mid+1,r,tl,tr);

		return min(get(x<<1,l,mid,tl,tr),get(x<<1|1,mid+1,r,tl,tr));

	}

	void ins(int x,int d){ins(1,1,n,x,d);}

	int get(int x,int y){return get(1,1,n,x,y);}

	int get(int x){return get(1,1,n,x,x);}

}

namespace Tr{

	vec e;

	Heap h[M];

	int pre[M],dep[M];

	int sz[M],son[M];

	int top[M],tdfn;

	int tid[M],pid[M];

	void dfs1(int x){

		int p,y;

		sz[x]=1; son[x]=0;

		for(p=e(x);p;p=e[p].nxt)

		if((y=e[p].y)!=pre[x]){

			dep[y]=dep[x]+1;

			pre[y]=x;

			dfs1(y);

			sz[x]+=sz[y];

			if(sz[y]>sz[son[x]]) son[x]=y;

		}

	}

	void dfs2(int x){

		int p,y;

		pid[tid[x]=++tdfn]=x;

		if(y=son[x]){

			top[y]=top[x];

			dfs2(y);

		}

		for(p=e(x);p;p=e[p].nxt)

		if((y=e[p].y)!=pre[x]&&y!=son[x]){

			top[y]=y;

			dfs2(y);

		}

	}

	void split(){

		pre[1]=0;dep[1]=1;

		dfs1(1);

		top[1]=1;tdfn=0;

		dfs2(1);

	}

	int LCA(int x,int y){

		while(top[x]!=top[y]){

			if(dep[top[x]]<dep[top[y]]) swap(x,y);

			x=pre[top[x]];

		}

		return dep[x]<dep[y]?x:y;

	}

	void mdf(int x,int pr,int nw){

		Seg::ins(tid[x],nw);

		if(pre[x]==0) return;

		if(pr>0) h[pre[x]].del(pr);

		h[pre[x]].ins(nw);

		Seg::ins(tid[pre[x]],h[pre[x]].top());

	}

	int get(int x,int y){

		int lca=LCA(x,y),res=INF;

		for(;dep[top[x]]>dep[lca];x=pre[top[x]])

			res=min(res,Seg::get(tid[top[x]],tid[x]));

		if(dep[x]>dep[lca])

			res=min(res,Seg::get(tid[lca]+1,tid[x]));

		for(;dep[top[y]]>=dep[lca];y=pre[top[y]])

			res=min(res,Seg::get(tid[top[y]],tid[y]));

		if(dep[y]>=dep[lca])

			res=min(res,Seg::get(tid[lca],tid[y]));

		if(lca>n&&pre[lca]) res=min(res,Seg::get(tid[pre[lca]]));

		return res;

	}

	void push(int x,int y){e.push2(x,y);}

}

namespace G{

	vec e;

	int dfn[M],low[M],tdfn;

	int stack[M],Top;

	int cnt;

	void BCC(int x,int fr){

		int p,y;

		dfn[x]=low[x]=++tdfn;

		stack[++Top]=x;

		for(p=e(x);p;p=e[p].nxt)

		if((y=e[p].y)!=fr){

			if(dfn[y]) low[x]=min(low[x],dfn[y]);

			else{

				BCC(y,x);

				low[x]=min(low[x],low[y]);

				if(low[y]>=dfn[x]){

					cnt++;

					Tr::push(x,cnt);

					do{Tr::push(cnt,stack[Top]);}while(y!=stack[Top--]);

				}

			}

		}

	}

	void push(int x,int y){e.push2(x,y);}

}

int main(){

	int i,x,y; char s[9];

	n=ri(),m=ri(),q=ri();

	for(i=1;i<=n;i++) val[i]=ri();

	for(i=1;i<=m;i++) G::push(ri(),ri());

	G::cnt=n;

	G::BCC(1,0);

	Seg::n=G::cnt;

	Tr::split();

	for(i=1;i<=n;i++) Tr::mdf(i,0,val[i]);

	for(i=1;i<=q;i++){

		scanf("%s",s);

		if(s[0]=='C'){

			x=ri(), y=ri();

			Tr::mdf(x,val[x],y);

			val[x]=y;

		}

		else if(s[0]=='A'){

			x=ri(),y=ri();

			printf("%d\n",Tr::get(x,y));

		}

	}

	return 0;

}

巴特西

cf 487E Tourist

题目大意

分析

做法

solution

最新文章

热门文章