某岛

… : "…アッカリ~ン . .. . " .. .
April 4, 2020

UOJ #55. 【WC2014】紫荆花之恋

https://t.me/algorithm_daily_of_minako/21
https://rqy.moe/Solutions/uoj55/
UOJ

LCA 的代码复制 这里
SBT 的代码复制 这里
都不太会写错,主要是动态树分治需要注意一点。第一名的代码 看起来是块状链表,这类题好像分块大法更快一些。
这种替罪羊的思想经常出现,比如 SRM 624 里 hard tourist 的做法,比如 SPOJ 9392. Play With Sequence

http://uoj.ac/submission/391176

const int N = int(1e5) + 9, M = 2*N, NN = 50*N, LV = 17;

namespace Raw_Tree {

    int hd[N], prd[M], suc[M], to[M]; int ww[N];
    int n, en;

    inline void add_edge(int x, int y) {
        suc[prd[hd[x]] = en] = hd[x]; to[en] = y; hd[x] = en++;
        suc[prd[hd[y]] = en] = hd[y]; to[en] = x; hd[y] = en++;
    }
    inline void del(int i){
        if (i == hd[to[i^1]]) prd[hd[to[i^1]] = suc[i]] = 0;
        else prd[suc[i]] = prd[i], suc[prd[i]] = suc[i];
    }
    inline void rec(int i) {
        if (suc[i] == hd[to[i^1]]) hd[to[i^1]] = prd[suc[i]] = i;
        else suc[prd[i]] = prd[suc[i]] = i;
    }

    int dep[N], dis[N], fa[N][17];
    void add(int u, int p, int w) {
        ww[en/2] = w; add_edge(u, p);
        dep[u] = dep[p] + 1; dis[u] = dis[p] + w;
        fa[u][0] = p; for (int lv=0;fa[u][lv+1]=fa[fa[u][lv]][lv];++lv);
    }
    inline int move_up(int x, int t){
        for (int lv=0;t;++lv,t>>=1)
            if (t&1) x = fa[x][lv];
        return x;
    }
    inline int lca(int x, int y) {
        if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
        DWN(lv, LV, 0) if (fa[x][lv]^fa[y][lv]) x = fa[x][lv], y = fa[y][lv];
        return fa[x][0];
    }
    inline int dist(int x, int y) {
        return dis[x] + dis[y] - 2*dis[lca(x,y)];
    }
} using namespace Raw_Tree;

namespace SBT {

    int c[2][NN], sz[NN], ky[NN];
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
    stack<int> pool;
    int new_node(int v = 0){
        int x=pool.top();pool.pop();lx=rx=0;
        sx=1;kx=v;
        return x;
    }
    void upd(int x){
        sx=sz[lx]+1+sz[rx];
    }
#undef d
    void rot(int &x,int d){
        int y=rx;rx=l[y];l[y]=x;
        upd(x),upd(y),x=y;
    }
    void fix(int &x,int d){
        if (sz[l[lx]] > sz[rx]) rot(x,!d);
        else{
            if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
            else return;
        }
        d=0,fix(lx,0),fix(rx,1);
        fix(x,0),fix(x,1);
    }
#define d 0
    void Ins(int &x,int v){
        if(!x) x = new_node(v);
        else{
            ++sz[x]; Ins(c[v>kx][x],v);
            fix(x,v>=kx);
        }
    }
    int d_key; void Del(int &x,int v){
        --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
            if(!lx||!rx) d_key = kx, x = lx | rx;
            else Del(lx,v+1), kx = d_key;
        }
        else Del(c[v>kx][x],v);
    }

    int Rank(int x,int v) {
        int z=0;while(x){
            if(kx<=v){
                z+=sz[lx]+1;
                x=rx;
            } else{
                x=lx;
            }
        }
        return z;
    }
    void clean(int& x) {
        if (!x) return;
        clean(lx); clean(rx);
        pool.push(x);
        x = 0;
    }
#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
};

int r[N];

namespace TDC {
    int T0[N], T1[N];
    int fa[N], sz[N], nn, cc, c;
    int vis[N], time; set<int> adj[N];

    void clean(int u) {
        vis[u] = time; SBT::clean(T0[u]);
        for (auto v: adj[u]) {
            SBT::clean(T1[v]);
            clean(v);
        }
        adj[u].clear();
    }

#define v to[i]
#define w ww[i/2]
    void dfsc(int u, int p = 0){
        int ss = 0; sz[u] = 1; REP_G(i, u) if (v != p){
            if (vis[v] != time) continue;
            dfsc(v, u), sz[u] += sz[v];
            checkMax(ss, sz[v]);
        }
        checkMax(ss, nn - sz[u]);
        if (ss <= cc) cc = ss, c = u;
    }

    void dfs0(int u, int p, int d, int& T) {
        SBT::Ins(T, d - r[u]);
        REP_G(i, u) if (v != p) {
            if (vis[v] != time) continue;
            dfs0(v, u, d+w, T);
        }
    }
    int divide(int u) {
        cc = nn; dfsc(u); u = c;
        dfs0(u, 0, 0, T0[u]);
        REP_G(i, u) {
            if (vis[v] != time) continue;
            del(i^1); int t = 0; dfs0(v, 0, w, t);
            nn = sz[v]; int vv = divide(v);
            rec(i^1); fa[vv] = u; adj[u].insert(vv); T1[vv] = t;
        }
        return u;
    }
#define p fa[u]
    void rebuild(int u) {
        int pp = p, tt = T1[u];
        ++time; nn = SBT::sz[T0[u]]; clean(u);
        adj[p].erase(u); u = divide(u); adj[p = pp].insert(u);
        T1[u] = tt;
    }
    LL add_leaf(int uu, int pp) {
        int u = uu;
        adj[p = pp].insert(u);
        LL z = 0; pp = 0;
        for (;u;u=p) {
            if (p) {
                int d = dist(p, uu);
                z += SBT::Rank(T0[p], r[uu] - d);
                z -= SBT::Rank(T1[u], r[uu] - d);
                SBT::Ins(T1[u], d - r[uu]);
                if (SBT::sz[T0[u]] > SBT::sz[T0[p]] * 0.75) pp = p;
            }
            int d = dist(u, uu);
            SBT::Ins(T0[u], d - r[uu]);
        }
        if (pp) rebuild(pp);
        return z;
    }
#undef p
#undef v
#undef w
};


int main() {

#ifndef ONLINE_JUDGE
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    DWN(i, NN, 1) SBT::pool.push(i);

    scanf("%*d%d", &n); REP_1(u, n) {
        int p, w; RD(p, w); RD(r[u]); p ^= last_ans % 1000000000; add(u, p, w);
        last_ans += TDC::add_leaf(u, p);
        printf("%lld\n", last_ans);
    }
}