2017-07-02

【清华集训2016】温暖会指引我们前行

本文为博主原创，未经许可不得转载

AC通道

根据kruskal算法，我们发现一个性质：最大生成树上的边是尽量大的

所以我们的做法非常显然：

对于温度维护一个最大生成树

于是这道题就和魔法森林一模一样了

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 400100
#define INF 1e9
using namespace std;
int n,m,cnt,value[MAXN],a[MAXN],pos[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
class Link_Cut_Tree{
	int f[MAXN],st[MAXN],rev[MAXN],mn[MAXN],sum[MAXN],son[MAXN][2],Link[MAXN][2];
	private:
		inline bool get(int x){return son[f[x]][1]==x;}
		inline bool isroot(int x){return son[f[x]][0]!=x&&son[f[x]][1]!=x;}
		inline void updata(int x){
			mn[x]=x;
			if(value[mn[son[x][0]]]<value[mn[x]])  mn[x]=mn[son[x][0]];
			if(value[mn[son[x][1]]]<value[mn[x]])  mn[x]=mn[son[x][1]];
			sum[x]=sum[son[x][0]]+sum[son[x][1]]+a[x];
		}
		inline void rotate(int x){
			int y=f[x],z=f[y],which=get(x);
			if(!isroot(y))  son[z][son[z][1]==y]=x;
			son[y][which]=son[x][which^1];  f[son[y][which]]=y;
			son[x][which^1]=y;  f[y]=x;  f[x]=z;
			updata(y);  updata(x);
		}
		inline void pushdown(int x){
			if(rev[x]){
				swap(son[x][0],son[x][1]);
				rev[son[x][0]]^=1; rev[son[x][1]]^=1;
				rev[x]=0;
			}
		}
		inline void splay(int x){
			int top(0);  st[++top]=x;
			for(int i=x;!isroot(i);i=f[i]) st[++top]=f[i];
			for(int i=top;i;--i) pushdown(st[i]);
			for(int y=f[x];!isroot(x);rotate(x),y=f[x])
				if(!isroot(y)) rotate(get(x)==get(y)?y:x);
		}
		inline void access(int x){
			int last=0;
			while(x){
				splay(x);
				son[x][1]=last;
				updata(x);
				last=x; x=f[x];
			}
		}
		inline void reverse(int x){
			access(x); splay(x); rev[x]^=1;
		}
		inline void linkk(int x,int y){
			reverse(x); reverse(y); f[y]=x; updata(x); 
		}
		inline void Cut(int x,int y){
			reverse(x); access(y); splay(y); 
			f[x]=son[y][0]=0; updata(y); updata(x);
		}
		inline int query(int x,int y){
			reverse(x); access(y); splay(y);
			return mn[y];
		}
		inline int find(int x){
			access(x); splay(x); while(son[x][0]) x=son[x][0];
			return x;
		}
	public:
		inline void insert(){
			int id=read(),x=read()+1,y=read()+1,v=read(),l=read();
			if(find(x)==find(y)){
				int temp=query(x,y);
				if(value[temp]>v) return;
				Cut(temp,Link[temp][0]); 
				Cut(temp,Link[temp][1]);
			}
			pos[id]=++cnt; value[pos[id]]=v; a[pos[id]]=l;
			linkk(pos[id],x);  linkk(pos[id],y);
			Link[pos[id]][0]=x;  Link[pos[id]][1]=y;
		}
		inline void change(){
			int id=read(),l=read();
			if(!pos[id]) return;
			access(pos[id]); splay(pos[id]);
			a[pos[id]]=l; updata(pos[id]);
		}
		inline void ask(){
			int x=read()+1,y=read()+1;
			if(find(x)!=find(y)) {puts("-1"); return;}
			reverse(x); access(y); splay(y);
			printf("%d\n",sum[y]);
		}
}Tree;
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=cnt=read();  m=read();
	for(int i=0;i<=n;++i) value[i]=INF;
	for(int i=1;i<=m;++i){
		char ch[10];  scanf("%s",ch);
		if(ch[0]=='f')  Tree.insert();
		else if(ch[0]=='c')  Tree.change();
		else Tree.ask();
	}
	return 0;
}

本文标题:【清华集训2016】温暖会指引我们前行

文章作者:chty

发布时间:2017年07月02日 - 15时20分

最后更新:2018年06月08日 - 18时49分

许可协议:本文为博主原创，未经许可不得转载。