UOJ#55. 【WC2014】紫荆花之恋
动态树分治 替罪羊树 treap 工业    2016-10-22 09:22:49    216    -7    2

#55. 【WC2014】紫荆花之恋

 统计

 

强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物,每个小精灵 ii 都有一个感受能力值 riri,小精灵 i,ji,j 成为朋友当且仅当在树上 ii 和 jj 的距离 dist(i,j)ri+rjdist(i,j)≤ri+rj,其中 dist(i,j)dist(i,j) 表示在这个树上从 ii 到 jj 的唯一路径上所有边的边权和。

强强和萌萌很好奇每次新长出一个叶子节点之后,这个树上总共有几对朋友。

我们假定这个树一开始为空,节点按照加入的顺序从 11 开始编号。由于强强非常好奇,你必须在他每次出现新结点后马上给出总共的朋友对数,不能拖延哦。

输入格式

第一行包含一个整数,表示测试点编号。

第二行包含一个正整数 nn,表示总共要加入的节点数。

我们令加入节点前的总共朋友对数是 last_anslast_ans,在一开始时它的值为 00

接下来 nn 行中第 ii 行有三个非负整数 ai,ci,riai,ci,ri,表示结点 ii 的父节点的编号为 aixor(last_ansmod109)aixor(last_ansmod109)(其中 xorxor 表示异或,modmod表示取余,数据保证这样操作后得到的结果介于 11到 i1i−1 之间),与父结点之间的边权为 cici,节点 ii 上小精灵的感受能力值为 riri

注意 a1=c1=0a1=c1=0,表示 11 号节点是根结点,对于 i>1i>1,父节点的编号至少为 11

输出格式

包含 nn 行,每行输出 11 个整数,表示加入第 ii 个点之后,树上有几对朋友。

样例一

input

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

output

0
1
2
4
7

样例二

见样例数据下载。

限制与约定

对于所有数据,满足 1ci100001≤ci≤10000ai2×10^9ai≤2×109ri10^9ri≤109

测试点编号约定
1, 2n100n≤100
3, 4n1000n≤1000
5, 6, 7, 8n100000n≤100000,节点 11 最多有两个子节点,其它节点最多有一个子节点
9, 10n100000n≤100000ri10ri≤10
11, 12n100000n≤100000,这棵树是随机生成的
13, 14, 15n70000n≤70000
16, 17, 18, 19, 20n100000n≤100000

此题 hack 时忽略输入数据中给定的测试点编号对测试点的限制。

祝大家一遍 AC,求不虐萌萌哒测评机!

时间限制:12s12s

空间限制512MB

 

Solution

 

假设这棵树是一棵深度为logN的随机树,我们考虑怎么得到答案:

首先式子的形式是Dis(i,j)<=Ri+Rj,变形得Dis(j,lca) – Rj <= Ri - Dis(i,lca)
那么对于每个lca我们维护一个平衡树,把以lca为根的子树中所有的Dis(j,lca)-Rj全都扔进去
然后对于每个i,我们沿着父亲指针,把路径上的所有小于等于Ri-Dis(i,lca)的全都计入答案,然后把Dis(i,p)-Ri加进路径上的平衡树 
但是这样算重复,即lca(i,j) != lca的情况,那么我们对于lca(I,j)的每个子树再维护一个平衡树储存Dis(j,p)-Rj,从对应子树的平衡树中减掉这样的点对就行了
但是树不是深度logN的随机树。。怎么办?
点分治树是平衡的!用树分治!
但是每次插入新节点,会导致树分治失效,怎么办?
用替罪羊树的思想,当点分治树不平衡时暴力重构即可。

 

于是我们得到了一个动态替罪羊点分治套双treap的做法
时间复杂度O(N log^2 N)
QwQ
 
/*{{{*/
#include <bits/stdc++.h>

#define VAL(x) #x " = " << x << " "

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

string program_name = __FILE__;
string iput = program_name.substr(0, program_name.length() - 4) + ".in";
string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }

template <class T> inline T &read(T &x) 
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) if (c == '-') f = -1;
    for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x *= f;
}

template <class T> void write(T x, char p = '\n') 
{
    register T tmp = 1;
    if (x < 0) putchar('-'), x = -x;
    while (x / tmp > 9) tmp *= 10;
    while (tmp) putchar(x / tmp + 48), x -= x / tmp * tmp, tmp /= 10;
    putchar(p);
}
/*}}}*/

const int maxn = 1e5 + 10;
const double ALPHA = 0.78;

// Gragh /*{{{*/
namespace Graph
{    struct edge { int to, f, next, ban; } e[maxn << 1];

    int head[maxn], tot = 1; 

    int ancestor[maxn][17], dpt[maxn], dis[maxn]; 

    inline void addedge(const int &u, const int &v, const int &w)
    {
        e[++ tot] = (edge) {v, w, head[u]};
        head[u] = tot;
    }

    inline void Build_LCA(const int &x)
    {
        for (int j = 1; j <= 16; ++ j)
            ancestor[x][j] = ancestor[ancestor[x][j - 1]][j - 1]; 
    }

    int LCA(int x, int y)
    {
        if (dpt[x] < dpt[y])
            swap(x, y); 

        for (int j = 16; ~j; -- j)
            if (dpt[ancestor[x][j]] >= dpt[y])
                x = ancestor[x][j];

        if (x == y) return x; 

        for (int j = 16; ~j; -- j)
            if (ancestor[x][j] != ancestor[y][j])
                x = ancestor[x][j], y = ancestor[y][j]; 

        return ancestor[x][0]; 
    }

    inline int Distance(const int &x, const int &y)
    {
        return dis[x] + dis[y] - 2 * dis[LCA(x, y)]; 
    }

}/*}}}*/

// Treap /*{{{*/
struct Treap
{
    static queue<Treap*> bin;

    Treap *ls, *rs; 
    int val, key; 
    int cnt, size; 

    inline void* operator new (size_t, int _)
    {
        static Treap *re;

        if (bin.size()) {
            re = bin.front(); 
            bin.pop(); 
        }
        else {
            static Treap *mempool, *C; 
            if (C == mempool)
                mempool = (C = new Treap[1 << 16]) + (1 << 16); // dynamic creation nodes.
            re = C ++; 
        }

        re->val = _; 
        re->key = rand();
        re->ls = re->rs = 0; 
        re->cnt = re->size = 1;

        return re; 
    }

    inline void operator delete (void *p)
    {
        bin.push((Treap*)p); 
    }

    inline void Push_Up()
    {
        size = cnt; 
        if (ls) size += ls->size; 
        if (rs) size += rs->size; 
    }

    friend inline void Zig(Treap *&x)
    {
        Treap *y = x->ls; 
        x->ls = y->rs; 
        y->rs = x; 
        x = y; 
        x->rs->Push_Up(); 
        x->Push_Up(); 
    }

    friend inline void Zag(Treap *&x)
    {
        Treap *y = x->rs; 
        x->rs = y->ls; 
        y->ls = x; 
        x = y; 
        x->ls->Push_Up(); 
        x->Push_Up(); 
    }

    friend void Insert(Treap *&x, int y)
    {
        if (x == 0) {
            x = new (y)Treap;
            return;
        }
        if (y == x->val) {
            ++ x->cnt;
        }
        else
            if (y < x->val) {
                Insert(x->ls, y);
                if(x->ls->key > x->key)
                    Zig(x);
            }
            else {
                Insert(x->rs, y);
                if (x->rs->key > x->key)
                    Zag(x);
            }
        x->Push_Up();
    }

    friend inline void Decomposition(Treap *&x)
    {
        if (x == 0) return;
        Decomposition(x->ls);
        Decomposition(x->rs);
        delete x;
        x = 0;
    }

    friend inline int Query(Treap *x, const int &y)
    {
        if (x == 0)
            return 0;
        if (y < x->val)
            return Query(x->ls, y);
        else
            return (x->ls ? x->ls->size : 0) + x->cnt + Query(x->rs, y);
    }

};

queue<Treap*> Treap::bin; 

/*}}}*/

long long ans; 

// Dynamic_Tree_Divide_and_Conquer_with_Scapegoat_Rebuild /*{{{*/
namespace Dynamic_Tree_Divide_and_Conquer_with_Scapegoat_Rebuild
{
    using namespace Graph; 

    int r[maxn]; 
    int fa[maxn], v[maxn], Time; 

    Treap *tree1[maxn], *tree2[maxn]; 

    set<int> to[maxn]; // I'm too lazy..

    static void DeleteSubtree(const int &x)
    {
        v[x] = Time; 
        for (set<int>::iterator it = to[x].begin(); it != to[x].end(); ++ it) {
            DeleteSubtree(*it);
            Decomposition(tree2[*it]);
        }
        to[x].clear();
        Decomposition(tree1[x]);
    }

    static int Get_Size(const int &x, const int &from)
    {
        int re = 1;
        for (int i = head[x]; i; i = e[i].next) {
            if (v[e[i].to] != Time)
                continue;
            if (e[i].ban == Time)
                continue;
            if (e[i].to == from)
                continue;
            re += Get_Size(e[i].to, x);
        }
        return re;
    }

    static int Get_Centre_Of_Gravity(const int &x, const int &from, const int &size, int &cg)
    {
        int cnt = 1, flag = true;

        for (int i = head[x]; i; i = e[i].next) {
            if (v[e[i].to] != Time)
                continue;
            if (e[i].ban == Time)
                continue;
            if (e[i].to == from)
                continue;

            int temp = Get_Centre_Of_Gravity(e[i].to, x, size, cg);

            if (temp * 2 > size)
                flag = false;

            cnt += temp;
        }

        if ((size - cnt) * 2 > size)
            flag = false;

        if (flag)
            cg = x;

        return cnt;
    }

    static void DFS(const int &x, const int &from, const int &dpt, Treap *&p)
    {
        Insert(p, dpt - r[x]);

        for (int i = head[x]; i; i = e[i].next) {
            if (v[e[i].to] != Time)
                continue;
            if (e[i].ban == Time)
                continue;
            if (e[i].to == from)
                continue;

            DFS(e[i].to, x, dpt + e[i].f, p);
        }
    }

    static int Tree_Divide_And_Conquer(int x)
    {
        int size=Get_Size(x, 0);

        Get_Centre_Of_Gravity(x, 0, size, x);
        DFS(x, 0, 0, tree1[x]);

        for (int i = head[x]; i; i = e[i].next) {
            if (v[e[i].to] != Time)
                continue;
            if (e[i].ban == Time)
                continue;

            Treap *p = NULL;
            DFS(e[i].to, x, e[i].f, p);

            e[i].ban = e[i ^ 1].ban = Time;

            int temp = Tree_Divide_And_Conquer(e[i].to);
            tree2[temp] = p;
            fa[temp] = x;
            to[x].insert(temp);

        }

        return x;
    }

    static void Rebuild(const int &x)
    {
        ++ Time;

        DeleteSubtree(x);
        int y = fa[x];
        Treap *p = tree2[x];
        tree2[x] = NULL;
        int temp = Tree_Divide_And_Conquer(x);
        fa[temp] = y;
        if (y)
            to[y].insert(temp);
        tree2[temp] = p;
    }

    void Insert(const int &x)
    {
        for (int i = x; i; i = fa[i]) {
            if (fa[i]) {
                int d1 = Distance(x, fa[i]);
                ans += Query(tree1[fa[i]], r[x] - d1);
                ans -= Query(tree2[i], r[x] - d1);
                Insert(tree2[i], d1 - r[x]);
            }

            int d = Distance(x, i);
            Insert(tree1[i], d - r[x]);
        }

        int to_rebuild = 0;

        for (int i = x; fa[i]; i = fa[i])
            if (tree1[i]->size > ALPHA * tree1[fa[i]]->size)
                to_rebuild = fa[i];

        if (to_rebuild)
            Rebuild(to_rebuild);
    }

}
/*}}}*/

int n; 

int main()
{
    if (fopen("3435.in", "r") != NULL) {
        freopen("3435.in", "r", stdin);
        freopen("3435.out", "w", stdout);
    }

    read(n); read(n);

    for (register int i = 1, fa, w, r; i <= n; ++ i) {
        read(fa);
        read(w);
        read(r);

        fa = fa ^ (ans % 1000000000);

        Graph::addedge(i, fa, w);
        Graph::addedge(fa, i, w);

        Graph::ancestor[i][0] = fa;
        Graph::dpt[i] = Graph::dpt[fa] + 1;
        Graph::dis[i] = Graph::dis[fa] + w;
        Graph::Build_LCA(i);

        Dynamic_Tree_Divide_and_Conquer_with_Scapegoat_Rebuild::r[i] = r;
        Dynamic_Tree_Divide_and_Conquer_with_Scapegoat_Rebuild::to[fa].insert(i);
        Dynamic_Tree_Divide_and_Conquer_with_Scapegoat_Rebuild::fa[i] = fa;
        Dynamic_Tree_Divide_and_Conquer_with_Scapegoat_Rebuild::Insert(i);

        write(ans);
    }

    return 0;
}
 

 

NOIP分治课件
216 人读过
立即登录, 发表评论.
没有帐号? 立即注册
2 条评论
文档导航