2016北京集训测试赛（十四）Problem B: 股神小D

Solution

正解是一个\(\log\)的link-cut tree. 将一条边拆成两个事件, 按照事件排序, link-cut tree维护联通块大小即可.

link-cut tree维护子树大小非常不熟练. 正确的做法是每个点开两个变量size和add, 分别表示在splay中以这个点为根的所有点所在的子树的点的数量, 以及以当前点为根的子树由虚边贡献的点的数量.

#include <cstdio>

#include <cctype>

#include <algorithm>

#define sort std::sort

#define swap std::swap

namespace Zeonfai

{

    inline int getInt()

    {

        int a = 0, sgn = 1; char c;

        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;

        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();

        return a * sgn;

    }

}

const int N = (int)2e5;

struct edge

{

    int u, v, pos, opt;

    inline edge() {}

    inline edge(int _u, int _v, int _pos, int _opt) {u = _u; v = _v; pos = _pos; opt = _opt;}

    inline int friend operator <(edge a, edge b)

    {

        return a.pos == b.pos ? a.opt < b.opt : a.pos < b.pos;

    }

}edg[N << 1];

struct linkCutTree

{

    struct node

    {

        node *pre, *suc[2];

        int isRoot, rev, sz, ad; // ad表示虚边连过来的大小, sz表示整颗辅助树的大小

        inline node() {pre = NULL; for(int i = 0; i < 2; ++ i) suc[i] = NULL; isRoot = sz = 1; rev = ad = 0;}

        inline int getRelation() {return isRoot ? -1 : this == pre->suc[1];}

        inline void update() {sz = ad + 1; for(int i = 0; i < 2; ++ i) if(suc[i] != NULL) sz += suc[i]->sz;}

        inline void reverse()

        {

            if(! isRoot) pre->reverse();

            if(rev)

            {

                swap(suc[0], suc[1]); rev = 0;

                for(int i = 0; i < 2; ++ i) if(suc[i] != NULL) suc[i]->rev ^= 1;

            }

        }

    }nd[N + 1];

    inline void rotate(node *u)

    {

        node *pre = u->pre, *prepre = u->pre->pre; int k = u->getRelation();

        if(u->suc[k ^ 1] != NULL) u->suc[k ^ 1]->pre = pre; pre->suc[k] = u->suc[k ^ 1];

        u->pre = prepre; if(! pre->isRoot) prepre->suc[pre->getRelation()] = u;

        u->suc[k ^ 1] = pre; pre->pre = u;

        if(pre->isRoot) u->isRoot = 1, pre->isRoot = 0;

        pre->update(); u->update();

    }

    inline void splay(node *u)

    {

        u->reverse();

        while(! u->isRoot)

        {

            if(! u->pre->isRoot) rotate(u->getRelation() == u->pre->getRelation() ? u->pre : u);

            rotate(u);

        }

    }

    inline void access(node *u)

    {

        splay(u);

        if(u->suc[1] != NULL) u->suc[1]->isRoot = 1, u->ad += u->suc[1]->sz, u->suc[1] = NULL;

        while(u->pre != NULL)

        {

            splay(u->pre);

            if(u->pre->suc[1] != NULL) u->pre->suc[1]->isRoot = 1, u->pre->ad += u->pre->suc[1]->sz;

            u->pre->suc[1] = u; u->pre->ad -= u->sz; u->isRoot = 0;

            splay(u);

        }

    }

    inline void makeRoot(node *u)

    {

        access(u); u->rev ^= 1;

    }

    inline long long link(int _u, int _v)

    {

        node *u = nd + _u, *v = nd + _v;

        makeRoot(u); makeRoot(v);

        long long res = (long long)u->sz * v->sz;

        v->pre = u; u->sz += v->sz; u->ad += v->sz;

        return res;

    }

    inline void cut(int _u, int _v)

    {

        node *u = nd + _u, *v = nd + _v;

        makeRoot(u); access(v);

        v->suc[0] = NULL; u->isRoot = 1; u->pre = NULL; v->sz -= u->sz;

    }

}LCT;

int main()

{

    #ifndef ONLINE_JUDGE

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

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

    #endif

    using namespace Zeonfai;

    int n = getInt();

    for(int i = 0, u, v, L, R; i < n - 1; ++ i) u = getInt(), v = getInt(), L = getInt(), R = getInt(), edg[i << 1] = edge(u, v, L, 1), edg[i << 1 | 1] = edge(u, v, R + 1, 0);

    sort(edg, edg + (n - 1 << 1));

    long long ans = 0;

    for(int i = 0; i < n - 1 << 1; ++ i) if(! edg[i].opt) LCT.cut(edg[i].u, edg[i].v); else ans += LCT.link(edg[i].u, edg[i].v);

    printf("%lld\n", ans);

}