BZOJ 4736 温暖会指引我们前行

题目大意

请你维护一个无向图，支持：加边，查询两点间最小边长瓶颈路径权值大小（权值和边长无关），更改边权。

首先求的是最小瓶颈路径，如果是纯静态的话直接求出最小生成树，在最小生成树求一下答案就可以了。

如果涉及动态加边那么就需要维护动态最小生成树——LCT维护。

注意LCT维护边权的方法是在路径两点间再新建一个点，点权为边权就可以了。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int ri()
{
	int ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp-'0'),tmp=nc();
	return ret;
}
inline char ric()
{
	char tmp=nc();
	while(!isalpha(tmp)) tmp=nc();
	return tmp;
}
#define N 1000010
int fa[N],c[N][2],mn[N],siz[N],len[N],temp[N],u[N],v[N],f[N];
bool rev[N];
inline bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
inline int colder(int x,int y){return temp[x]<temp[y]?x:y;}
inline void pushup(int x)
{
	mn[x]=colder(x,colder(mn[c[x][0]],mn[c[x][1]]));
	siz[x]=siz[c[x][0]]+siz[c[x][1]]+len[x];
}
inline void pushdown(int x)
{
	if(rev[x])
	{
		rev[c[x][0]]^=1,rev[c[x][1]]^=1,rev[x]^=1;
		swap(c[c[x][0]][0],c[c[x][0]][1]);
		swap(c[c[x][1]][0],c[c[x][1]][1]);
	}
}
void init(int x)
{
	if(!isroot(x)) init(fa[x]);
	pushdown(x);
}
inline void rotate(int x)
{
	int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
	if(!isroot(y)) c[z][c[z][1]==y]=x;
	fa[x]=z,fa[y]=x,fa[c[x][r]]=y,c[y][l]=c[x][r],c[x][r]=y;
	pushup(y),pushup(x);
}
inline void splay(int x)
{
	init(x);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if((c[y][1]==x)^(c[z][1]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
inline void access(int x)
{
	int t=0;
	while(x) splay(x),c[x][1]=t,pushup(x),t=x,x=fa[x];
}
inline void chroot(int x)
{
	access(x),splay(x);
	swap(c[x][0],c[x][1]),rev[x]^=1;
}
inline void link(int x,int y)
{
	//printf("Link %d %d \n",x,y);
	chroot(x),fa[x]=y;
}
inline void cut(int x,int y)
{
	//printf("Cut %d %d \n",x,y);
	chroot(x),access(y),splay(y);
	c[y][0]=fa[x]=0;
	pushup(x),pushup(y);
}
int unifind(int x){return (f[x]==x)?x:f[x]=unifind(f[x]);}
int main()
{
	int n=ri(),m=ri();
	for(int i=0;i<=n;++i) f[i]=i,temp[i]=0x3f3f3f3f;
	int id,x,y,t;
	while(m--)
	{
		switch(ric())
		{
			case 'f':
			{
				id=n+ri()+1,u[id]=ri()+1,v[id]=ri()+1,temp[id]=ri(),len[id]=ri();
				if(unifind(u[id])!=unifind(v[id])) f[unifind(u[id])]=f[unifind(v[id])],link(u[id],id),link(id,v[id]);
				else if(chroot(u[id]),access(v[id]),splay(v[id]),temp[mn[v[id]]]<temp[id])
				{
					t=mn[v[id]];
					cut(u[t],t),cut(t,v[t]);
					link(u[id],id),link(id,v[id]);
				}
				break;
			}
			case 'm':
			{
				x=ri()+1,y=ri()+1;
				if(unifind(x)!=unifind(y)) puts("-1");
				else chroot(x),access(y),splay(y),printf("%d\n",siz[y]);
				break;
			}
			case 'c':x=n+ri()+1,splay(x),len[x]=ri(),pushup(x);break;
		}
	}
	return 0;
}