BZOJ4736 温暖会指引我们前行（LCT+最大生成树）

　　类似于瓶颈路，满足条件的路径一定在温度的最大生成树上，那么就是一个LCT维护MST的裸题了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

#define M 300010

#define inf 1000000001

#define lson tree[k].ch[0]

#define rson tree[k].ch[1]

#define lself tree[tree[k].fa].ch[0]

#define rself tree[tree[k].fa].ch[1]

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,cnt,w[N+M][],id[M],temp[N+M];

struct data{int ch[],fa,rev,len,sum,id;

}tree[N+M];

void up(int k)

{

    tree[k].sum=tree[lson].sum+tree[rson].sum+tree[k].len;

    tree[k].id=k;

    if (temp[tree[lson].id]<temp[tree[k].id]) tree[k].id=tree[lson].id;

    if (temp[tree[rson].id]<temp[tree[k].id]) tree[k].id=tree[rson].id;

}

void rev(int k){if (k) swap(lson,rson),tree[k].rev^=;}

void down(int k){if (tree[k].rev) rev(lson),rev(rson),tree[k].rev=;}

bool isroot(int k){return lself!=k&&rself!=k;}

int whichson(int k){return rself==k;}

void push(int k){if (!isroot(k)) push(tree[k].fa);down(k);}

void move(int k)

{

    int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k);

    if (!isroot(fa)) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf;

    tree[fa].ch[p]=tree[k].ch[!p],tree[tree[k].ch[!p]].fa=fa;

    tree[k].ch[!p]=fa,tree[fa].fa=k;

    up(fa),up(k);

}

void splay(int k)

{

    push(k);

    while (!isroot(k))

    {

        int fa=tree[k].fa;

        if (!isroot(fa))

            if (whichson(k)^whichson(fa)) move(k);

            else move(fa);

        move(k);

    }

}

void access(int k){for (int t=;k;t=k,k=tree[k].fa) splay(k),tree[k].ch[]=t,up(k);}

int findroot(int k){access(k),splay(k);for (;lson;k=lson) down(k);splay(k);return k;}

void makeroot(int k){access(k),splay(k),rev(k);}

void link(int x,int y){makeroot(x),tree[x].fa=y;}

void cut(int x,int y){makeroot(x),access(y),splay(y),tree[y].ch[]=tree[x].fa=,up(y);}

int queryid(int x,int y){makeroot(x),access(y),splay(y);return tree[y].id;}

int querylen(int x,int y){makeroot(x),access(y),splay(y);return tree[y].sum;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4736.in","r",stdin);

    freopen("bzoj4736.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) temp[i]=inf,tree[i].id=i;cnt=n;

    for (int i=;i<=m;i++)

    {

        char c=getc();

        if (c=='f')

        {

            int u=read(),x=read()+,y=read()+,t=read(),l=read();

            if (findroot(x)==findroot(y))

            {

                int p=queryid(x,y);

                if (temp[p]>=t) continue;

                cut(p,w[p][]),cut(p,w[p][]);

                w[p][]=w[p][]=;

            }

            id[u]=++cnt;temp[id[u]]=t,tree[id[u]].len=tree[id[u]].sum=l,tree[id[u]].id=id[u],w[id[u]][]=x,w[id[u]][]=y;

            link(id[u],x),link(id[u],y);

        }

        if (c=='m')

        {

            int x=read()+,y=read()+;

            if (findroot(x)!=findroot(y)) printf("-1\n");

            else printf("%d\n",querylen(x,y));

        }

        if (c=='c')

        {

            int u=read(),l=read();

            if (w[id[u]][])

            {

                cut(id[u],w[id[u]][]),cut(id[u],w[id[u]][]);

                tree[id[u]].len=tree[id[u]].sum=l;

                link(id[u],w[id[u]][]),link(id[u],w[id[u]][]);

            }

        }

    }

    return ;

}