暖气来啦~
动态树维护最大生成树裸题
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int maxn=;
int es[maxn][];
int n,m;
int rt,Size;
struct LCT
{
int son[maxn][],f[maxn],val[maxn],size[maxn],cnt[maxn],rev[maxn],st[maxn];
int t[maxn],len[maxn],mn[maxn],sum[maxn];
inline void update(int x)
{
int &o=x,lch=son[x][],rch=son[x][];
mn[o]=x;sum[o]=len[o];
if(son[x][])
{
if(t[mn[lch]]<t[mn[x]]) mn[o]=mn[lch];
sum[o]+=sum[lch];
}
if(son[x][])
{
if(t[mn[rch]]<t[mn[x]]) mn[o]=mn[rch];
sum[o]+=sum[rch];
}
}
inline int isroot(int x){return son[f[x]][]!=x && son[f[x]][]!=x;}
inline void rotate(int x)
{
int y=f[x],z=f[y],l,r;
if(son[y][]==x)l=;
else l=;r=l^;
if(!isroot(y))
{
if(son[z][]==y)son[z][]=x;
else son[z][]=x;
}
f[x]=z;f[y]=x;f[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
update(y);
}
inline void pushdown(int id)
{
int lch=son[id][],rch=son[id][];
if(rev[id])
{
rev[id]^=;rev[lch]^=;rev[rch]^=;
swap(son[id][],son[id][]);
}
}
inline void Splay(int x)
{
int top=;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]);
while(!isroot(x))
{
int y=f[x],z=f[y];
if(!isroot(y))
{
if(son[y][]==x^son[z][]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
update(x);
}
inline void access(int x)
{
int t=;
while(x)
{
Splay(x);
son[x][]=t;
t=x;
x=f[x];
update(x);
}
}
inline void makert(int x){access(x);Splay(x);rev[x]^=;}
inline void link(int x,int y){makert(x);f[x]=y;}
inline void cut(int x,int y){makert(x);access(y);Splay(y);son[y][]=f[x]=;update(y);}
inline int findf(int x)
{
access(x);Splay(x);
int y=x;
while(son[y][])y=son[y][];
return y;
}
}Tree;
char opt[];
int main()
{
scanf("%d%d",&n,&m);
int k,x,y,z;
for(int i=;i<=n;i++)Tree.t[i]=;
while(m--)
{
scanf("%s",opt);
if(opt[]=='f')
{
scanf("%d%d%d",&z,&x,&y);z++,x++,y++;
z+=n;es[z][]=x,es[z][]=y;
scanf("%d%d",&Tree.t[z],&Tree.len[z]);
if(Tree.findf(x)!=Tree.findf(y)){Tree.link(z,x),Tree.link(z,y);}
else
{
Tree.makert(x);Tree.access(y);Tree.Splay(y);
if(Tree.t[Tree.mn[y]]<Tree.t[z])
{
k=Tree.mn[y];Tree.cut(k,es[k][]);Tree.cut(k,es[k][]);
Tree.link(z,x),Tree.link(z,y);
}
}
}
else if(opt[]=='m')
{
scanf("%d%d",&x,&y);x++,y++;
if(Tree.findf(x)!=Tree.findf(y))puts("-1");
else
{
Tree.makert(x);Tree.access(y);Tree.Splay(y);
printf("%d\n",Tree.sum[y]);
}
}
else
{
scanf("%d%d",&x,&y);x++;
x+=n;Tree.Splay(x);Tree.len[x]=y;Tree.update(x);
}
}
}