The Preliminary Contest for ICPC Asia Shanghai 2019 A. Lightning Routing I

传送门

因为某些原因，所以我就去学了 $LCT$ 维护直径， $LCT$ 维护直径我上一个博客讲得很详细了：传送门

这里维护虚儿子用的是 $multiset$ ，没写可删堆

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<set>

#include<queue>

using namespace std;

typedef long long ll;

inline int read()

{

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

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

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=8e5+;

const ll INF=1e18;

int n,m;

struct edge {

    int x,y;

}e[N];

namespace LCT {

    int c[N][],fa[N],sz[N],val[N];

    ll sum[N],lmx[N],rmx[N],mxs[N];

    bool rev[N];

    multiset <ll> H[N],P[N];

    inline void ins(int u,int v) { H[u].insert(lmx[v]); P[u].insert(mxs[v]); }

    inline void del(int u,int v) { H[u].erase(H[u].find(lmx[v])); P[u].erase(P[u].find(mxs[v])); }

    inline ll fir(multiset <ll> &S) { return S.size() ? *S.rbegin() : -INF; }

    inline ll sec(multiset <ll> &S) { return S.size()> ? *(++S.rbegin()) : -INF; }

    inline void pushup(int x)

    {

        int &lc=c[x][],&rc=c[x][];

        sum[x]=sum[lc]+sum[rc]+val[x];

        ll t=max(0ll,fir(H[x])), L=max(t,rmx[lc])+val[x], R=max(t,lmx[rc])+val[x];

        lmx[x]=max(lmx[lc], sum[lc]+R ); rmx[x]=max(rmx[rc], sum[rc]+L );

        mxs[x]=max( max( rmx[lc]+R , lmx[rc]+L ) , max(mxs[lc],mxs[rc]) );

        mxs[x]=max(mxs[x],fir(P[x])); mxs[x]=max(mxs[x], t+val[x] );

        mxs[x]=max(mxs[x], t+val[x]+sec(H[x]) );

    }

    inline void pushdown(int x)

    {

        if(!x||!rev[x]) return;

        int &lc=c[x][],&rc=c[x][]; rev[x]=;

        swap(lc,rc); swap(lmx[x],rmx[x]);

        if(lc) rev[lc]^=;

        if(rc) rev[rc]^=;

    }

    inline void rever(int x) { rev[x]=; pushdown(x); }

    inline bool noroot(int x) { return (c[fa[x]][]==x)|(c[fa[x]][]==x); }

    inline void rotate(int x)

    {

        int y=fa[x],z=fa[y],d=(c[y][]==x);

        if(noroot(y)) c[z][c[z][]==y]=x;

        fa[x]=z; fa[y]=x; fa[c[x][d^]]=y;

        c[y][d]=c[x][d^]; c[x][d^]=y;

        pushup(y);

    }

    void push_rev(int x)

    {

        if(noroot(x)) push_rev(fa[x]);

        else pushdown(x);

        pushdown(c[x][]); pushdown(c[x][]);

    }

    inline void splay(int x)

    {

        push_rev(x);

        while(noroot(x))

        {

            int y=fa[x],z=fa[y];

            if(noroot(y))

                (c[y][]==x ^ c[z][]==y) ? rotate(x) : rotate(y);

            rotate(x);

        } pushup(x);

    }

    inline void access(int x)

    {

        for(int y=;x;y=x,x=fa[x])

        {

            splay(x); if(y) del(x,y);

            if(c[x][]) ins(x,c[x][]);

            c[x][]=y; pushup(x);

        }

    }

    inline void makeroot(int x) { access(x); splay(x); rever(x); }

    inline int findroot(int x)

    {

        access(x); splay(x); pushdown(x);

        while(c[x][]) x=c[x][],pushdown(x);

        splay(x); return x;

    }

    inline void split(int x,int y) { makeroot(x); access(y); splay(y); }

    inline void link(int x,int y)

    {

        makeroot(x); if(findroot(y)==x) return;

        makeroot(y); fa[x]=y; ins(y,x); pushup(y);

    }

    inline void cut(int x,int y)

    {

        makeroot(x);

        if(findroot(y)!=x||fa[y]!=x||c[y][]) return;

        fa[y]=c[x][]=; pushup(x);

    }

    inline void Link(int k) { link(e[k].x,n+k); link(e[k].y,n+k); }

    inline void Cut(int k) { cut(e[k].x,n+k); cut(e[k].y,n+k); }

    inline ll query(int x) { access(x); splay(x); return rmx[x]; }

}

int main()

{

    n=read();

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

        e[i].x=read(),e[i].y=read(),LCT::val[n+i]=read();

    for(int i=;i<n;i++) LCT::Link(i);

    m=read(); char s[]; int a;

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

    {

        scanf("%s",s); a=read();

        if(s[]=='Q') printf("%lld\n",LCT::query(a));

        else LCT::Cut(a),LCT::val[n+a]=read(),LCT::Link(a);

    }

    return ;

}