【luoguP3920】[WC2014]紫荆花之恋

n m d, w s m,劳资就是头铁,过了233333333333333333333
这个破题简直司马。
首先这个式子很好变化
Dis_{i}表示目前i这个点到根的距离。
Dis_{i}+Dis_{j}-2Dis_{lca(i,j)} \leq r_{i} + r_{j}
那么
Dis_{i} – r_{i}-Dis_{lca(i,j)} \leq r_{j} – Dis_{j} + Dis_{lca(i,j)}
然后你就直接把每个点都当lca来看的话,把左右两边的值插进u这个点的平衡树就好了,注意因为你要查询它的父亲,所以要把子树的信息传上来,建两个平衡树,这是因为假如你到达了lca的父亲,思考下,如果直接查询子树信息,这里会计算deep[lca]次。再外面套个点分树,复杂度O(nlog^2n)
说着挺简单的,维护贼·t·m·恶·心。
首先你的平衡树就不能写splay/fhq,因为这俩哥们太慢。
treap不会,那么剩下最好写的就是替罪羊了。
替罪羊之前扯过。
那么就算你第一层替罪羊写完了,接下来的点分树还是动态的。
那么第二个好像也需要平衡,所以再套一层替罪羊树。可是问题是,如果我们只对点分树的一部分进行重构了,怎么办?
记录每个点在自己父亲儿子中的顺序,每次修改的时候找出Root,然后直接按照它在父亲的顺序进行O(1)的修改。
剩下的细节代码里有,不再详细叙述,大概破了学oi以来写的最长的正解(数据分治暴力不算)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = gch();
    if(b == 1)
        x = - x;
}

const int ms = 1e5 + 10, Ms = 1e7 + 10;

const double Alpha = 0.8;

int n, lx, ly, lz;

lo lastans;

struct Dt
{
    struct Tree//树本身
    {
        int de[ms], fa[ms], dis[ms][105], sz[ms];

        unsigned h[ms];

        vector <int> a[ms];
    }tre;

    struct edge
    {
        int to, co;
    };

    vector <edge> a[ms];

    int n, cnt, Root, r[ms], w[ms], sz[ms];

    bool flag[ms];

    struct Sgt
    {
        int val[Ms], ch[Ms][2], sz[Ms], sonroot[ms], faroot[ms], Top, mem[Ms], tot, tmp[ms];

        void init(int tot)
        {
            Top = 0;
            for(ri i = tot; i; i --)
                mem[++ Top] = i;
        }

        int newnode(int v)
        {
            int t = mem[Top --]; val[t] = v, sz[t] = 1, ch[t][0] = 0, ch[t][1] = 0;
            return t;
        }

        void dfs(int pos)//准备拍扁重建
        {
            mem[++ Top] = pos;
            if(ch[pos][0])
                dfs(ch[pos][0]);
            tmp[++ tot] = val[pos];//这里是为了严格按照中序遍历
            if(ch[pos][1])
                dfs(ch[pos][1]);
        }

        int rebuild(int l, int r)
        {
            if(l == r)
                return newnode(tmp[l]);
            int mid = (l + r) >> 1, rt = newnode(tmp[mid]);
            sz[rt] = r - l + 1;
            if(mid > l)
                ch[rt][0] = rebuild(l, mid - 1);
            if(mid < r)
                ch[rt][1] = rebuild(mid + 1, r);
            return rt;
        }

        inline int Rebuild(int Rt, int v)//拍扁重建
        {
            tot = 0, dfs(Rt); bool fl = 1;
            for(ri i = 1; i <= tot; i ++)
                if(tmp[i] >= v)
                {
                    tot ++;
                    for(ri j = tot; j > i; j --)
                        tmp[j] = tmp[j - 1];
                    tmp[i] = v, fl = 0; break;
                }
            if(fl)
                tmp[++ tot] = v;
            return rebuild(1, tot);
        }

        void insert(int &x, int v)//替罪羊的重建过程
        {
            if(!x)
            {
                x = newnode(v); return;
            }
            sz[x] ++;
            if(v < val[x])
            {
                if(sz[ch[x][0]] > sz[x] * Alpha)
                    x = Rebuild(x, v);
                else
                    insert(ch[x][0], v);
            }
            else
            {
                if(sz[ch[x][1]] > sz[x] * Alpha)
                    x = Rebuild(x, v);
                else
                    insert(ch[x][1], v);
            }
        }

        void restore(int x)
        {
            mem[++ Top] = x;
            if(ch[x][0])
                restore(ch[x][0]);
            if(ch[x][1])
                restore(ch[x][1]);
        }

        int ask(int x, int v)
        {
            if(x == 0)
                return 0;
            if(v < val[x])
                return ask(ch[x][0], v);
            return ask(ch[x][1], v) + sz[ch[x][0]] + 1;
        }

        void faclear(int x)
        {
            if(faroot[x])
                restore(faroot[x]);
            faroot[x] = 0;
        }

        void sonclear(int x)
        {
            if(sonroot[x])
                restore(sonroot[x]);
            sonroot[x] = 0;
        }

        void fainsert(int x, int v)
        {
            insert(faroot[x], v);
        }

        void soninsert(int x, int v)
        {
            insert(sonroot[x], v);
        }

        int faask(int x, int v)
        {
            return ask(faroot[x], v);
        }

        int sonask(int x, int v)
        {
            return ask(sonroot[x], v);
        }

        void Give(int f, int t)
        {
            sonroot[t] = sonroot[f], sonroot[f] = 0;
        }
    }sgt;

    void init(int x, int y)
    {
        tre.a[0].push_back(0), tre.de[1] = 1, n = x, r[1] = y; 
        w[0] = n + 1, sgt.init(Ms - 1), sgt.fainsert(1, -y);
    }

    void dfs(int x)
    {
        cnt ++; flag[x] = 1; int Si = tre.a[x].size();
        for(ri i = 0; i < Si; i ++)
            dfs(tre.a[x][i]);
    }

    void askroot(int no, int f, int S)
    {
        sz[no] = 1, w[no] = 0; int to, Si = a[no].size();
        for(ri i = 0; i < Si; i ++)
            if((to = a[no][i].to) != f && flag[to])
                askroot(to, no, S), sz[no] += sz[to], w[no] = max(w[no], sz[to]);
        w[no] = max(w[no], S - sz[no]);
        if(w[no] < w[Root])
            Root = no;
    }

    void reasksz(int no, int f)//重新计算size
    {
        sz[no] = 1; int to, Si = a[no].size();
        for(ri i = 0; i < Si; i ++)
            if((to = a[no][i].to) != f && flag[to])
                reasksz(to, no), sz[no] += sz[to];
    }

    void reask(int no, int f, int fr, int d, int c)
    {
        int to;
        tre.sz[fr] ++, tre.dis[no][d] = c;
        sgt.fainsert(fr, c - r[no]), sgt.soninsert(Root, c - r[no]);
        for(ri i = 0; i < a[no].size(); i ++)
            if((to = a[no][i].to) != f && flag[to])
                reask(to, no, fr, d, c + a[no][i].co);
    }

    void Work(int no, int d, int tot)//具体的重构过程
    {
        tre.a[no].clear(), flag[no] = 0, tre.de[no] = d, sgt.faclear(no);
        sgt.fainsert(no, -r[no]), reasksz(no, 0), tre.sz[no] = 1, tre.dis[no][d] = 0;
        int Si = a[no].size(), to, ci = 0;
        for(ri i = 0; i < Si; i ++)
            if(flag[to = a[no][i].to])
                Root = 0, askroot(to, 0, sz[to]), sgt.sonclear(Root), reask(to, no, no, d, a[no][i].co);
        for(ri i = 0; i < Si; i ++)
            if(flag[to = a[no][i].to])//记录所有点在自己点分树上父亲,儿子的顺序
                Root = 0, askroot(to, 0, sz[to]), tre.fa[Root] = no, tre.a[no].push_back(Root), tre.h[Root] = ci, ci ++, Work(Root, d + 1, sz[to]);
    }

    void rebuild(int no)//对最大的不合法的点分树进行重构
    {
        cnt = 0, dfs(no), Root = 0, askroot(no, 0, cnt);
        tre.a[tre.fa[no]][tre.h[no]] = Root, tre.fa[Root] = tre.fa[no];//通过记录原来这个点儿子所在位置,对于没修改的点分树进行快速的对儿子的维护
        sgt.Give(no, Root), Work(Root, tre.de[no], cnt);
    }

    int insert(int no, int x, int y, int z)//插入到真实的树上
    {
        a[no].push_back((edge){x, y}), a[x].push_back((edge){no, y}); 
        r[no] = z, tre.sz[no] = 1, tre.fa[no] = x, tre.de[no] = tre.de[x] + 1;
        tre.a[x].push_back(no), tre.h[no] = tre.a[x].size() - 1;//h记录在父亲的位置?
        tre.dis[no][tre.de[no]] = 0, sgt.fainsert(no, -z);//这个dis应该是利用的随机树高不会超过logn……看脸看脸
        int No = no, las = no, rt = 0;
        for(ri i = tre.de[no] - 1; i; i --)
        {
            las = No, No = tre.fa[No], tre.sz[No] ++;
            tre.dis[no][i] = tre.dis[x][i] + y;//就直接复制点分树的距离
            sgt.fainsert(No, tre.dis[no][i] - z), sgt.soninsert(las, tre.dis[no][i] - z);
            if(tre.sz[las] > tre.sz[No] * Alpha + 1)
                rt = No;
        }
        if(rt)
            rebuild(rt);
        int ans = sgt.faask(no, z) - 1;
        No = no, las = no;
        for(ri i = tre.de[no] - 1; i; i --)
            las = No, No = tre.fa[No], ans += sgt.faask(No, z - tre.dis[no][i]), ans -= sgt.sonask(las, z - tre.dis[no][i]);
        return ans;
    }
}dt;

int main()
{
    re(n), re(n), re(lx), re(ly), re(lz), dt.init(n, lz);
    puts("0");
    for(ri i = 2; i <= n; i ++)
        re(lx), re(ly), re(lz), lx ^= (lastans % 1000000000), lastans += dt.insert(i, lx, ly, lz), printf("%lld\n", lastans);
}