【BZOJ2959】长跑（Link-Cut Tree，并查集）

时间：2021-12-21 21:33:45

【BZOJ2959】长跑（Link-Cut Tree，并查集）

题面

BZOJ

题解

如果保证不出现环的话

妥妥的\(LCT\)傻逼题

现在可能会出现环

环有什么影响？

那就可以沿着环把所有点全部走一遍吧

所以，相当于把环看成一个点来搞一搞

所以，维护一个并查集

记录一下每个点被缩成了哪个点

然后再用\(LCT\)维护缩点后的树就行啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 320000

#define lson (t[x].ch[0])

#define rson (t[x].ch[1])

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Node

{

	int ch[2],ff;

	int sum,rev,v;

}t[MAX<<1];

int S[MAX<<1],top;

int tot,n,m,a[MAX<<1];

int f[MAX<<1];

int ff[MAX<<1];

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

int Getf(int x){return x==ff[x]?x:ff[x]=Getf(ff[x]);}

bool isroot(int x){return t[getf(t[x].ff)].ch[0]!=x&&t[getf(t[x].ff)].ch[1]!=x;}

void pushup(int x){t[x].sum=t[lson].sum+t[rson].sum+t[x].v;}

void pushdown(int x)

{

	if(!t[x].rev)return;

	swap(lson,rson);

	t[lson].rev^=1;t[rson].rev^=1;

	t[x].rev^=1;

}

void rotate(int x)

{

    int y=getf(t[x].ff),z=getf(t[y].ff);

    int k=t[y].ch[1]==x;

    if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;

    t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;

    t[x].ch[k^1]=y;t[y].ff=x;

    pushup(y);pushup(x);

}

void Splay(int x)

{

    S[top=1]=x=getf(x);

    for(int i=x;!isroot(i);i=getf(t[i].ff))S[++top]=getf(t[i].ff);

    while(top)pushdown(S[top--]);

    while(!isroot(x))

    {

        int y=getf(t[x].ff),z=getf(t[y].ff);

        if(!isroot(y))

            (t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);

        rotate(x);

    }

}

void access(int x){x=getf(x);for(int y=0;x;y=x,x=getf(t[x].ff))Splay(x),t[x].ch[1]=y,pushup(x);}

void makeroot(int x){x=getf(x);access(x);Splay(x);t[x].rev^=1;}

void split(int x,int y){x=getf(x);y=getf(y);makeroot(x);access(y);Splay(y);}

void link(int x,int y){x=getf(x);y=getf(y);makeroot(x);t[x].ff=y;pushup(y);}

int findroot(int x){getf(x);access(x);Splay(x);while(lson)x=lson;return x;}

void dfs(int x)

{

	f[getf(x)]=tot;

	t[tot].v+=t[x].v;

	t[tot].sum+=t[x].v;

	if(lson)dfs(lson);

	if(rson)dfs(rson);

}

void Link(int x,int y)

{

	if(Getf(x)!=Getf(y))ff[Getf(x)]=Getf(y),link(getf(x),getf(y));

	else

	{

		x=getf(x);y=getf(y);

		++tot;ff[tot]=f[tot]=tot;

		split(x,y);

		dfs(y);

	}

}

void Modify(int u,int v)

{

	makeroot(getf(u));

	t[getf(u)].v-=a[u];a[u]=v;

	t[getf(u)].v+=a[u];

	pushup(getf(u));

}

int Query(int u,int v)

{

	if(Getf(u)!=Getf(v))return -1;

	u=getf(u);v=getf(v);

	split(u,v);

	return t[v].sum;

}

int main()

{

	tot=n=read();m=read();

	for(int i=1;i<=n;++i)f[i]=ff[i]=i,t[i].v=a[i]=read();

	int opt,u,v;

	while(m--)

	{

		opt=read();u=read();v=read();

		if(opt==1)Link(u,v);

		else if(opt==2)Modify(u,v);

		else printf("%d\n",Query(u,v));

	}

	return 0;

}

相关文章