紫荆花之恋

#include <ctime>
#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <algorithm>
#include <vector>
#include <queue>
#include <set>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct Edge {
    int v, w;
    Edge* next;
};

const int N = 100010, LGN = 20, LGAN = 47;

struct Treap {
    struct Node {
        static Node* reuse[N * LGAN];
        static int rcnt;

        ll v;
        int cnt, rnd;
        union {
            struct {
                Node *ls, *rs;
            };
            Node* ch[2];
        };
        Node* prt;

        inline void release() {
            LOG("REL %d\n", rcnt + 1);
            reuse[rcnt++] = this;
            if (ls)
                ls->release();
            if (rs)
                rs->release();
        }

        inline bool relation() {
            return this == prt->rs;
        }

        inline void update() {
            cnt = 1;
            if (ls)
                cnt += ls->cnt;
            if (rs)
                cnt += rs->cnt;
        }

        inline void rotate() {
            Node* p = prt;
            bool f = relation();
            if (prt->prt)
                prt->prt->ch[prt->relation()] = this;
            prt = p->prt;
            p->ch[f] = ch[!f];
            if (ch[!f])
                ch[!f]->prt = p;
            p->prt = this;
            ch[!f] = p;
            p->update();
            update();
        }

        inline int count(ll key) {
            Node* p = this;
            int ret = 0;
            while (p) {
                if (p->v <= key) {
                    ret += 1;
                    if (p->ls)
                        ret += p->ls->cnt;
                    p = p->rs;
                } else
                    p = p->ls;
            }
            return ret;
        }

        inline void insert(Node* p) {
            while (true) {
                if (p->v <= v) {
                    if (p->rs)
                        p = p->rs;
                    else {
                        p->rs = this;
                        prt = p;
                        break;
                    }
                } else {
                    if (p->ls)
                        p = p->ls;
                    else {
                        p->ls = this;
                        prt = p;
                        break;
                    }
                }
            }
            while (p) {
                p->update();
                p = p->prt;
            }
        }

        void ord() {
            if (ls)
                ls->ord();
            LOG("%lld ", v);
            if (rs)
                rs->ord();
        }
    };

    Node* root;

    ~Treap() {
        if (root)
            root->release();
    }

    inline void clear() {
        if (root)
            root->release();
        root = NULL;
    }

    inline void insert(ll v) {
        static Node pool[N * LGAN];
        static Node* ptop = pool;
        Node* p;
        if (Node::rcnt != 0)
            p = Node::reuse[--Node::rcnt];
        else
            p = ptop++;
        p->v = v;
        p->cnt = 1;
        p->rnd = rand();
        p->ls = p->rs = p->prt = NULL;
        if (!root)
            root = p;
        else {
            p->insert(root);
            while (p->prt && p->rnd < p->prt->rnd)
                p->rotate();
            if (!p->prt)
                root = p;
        }
    }

    inline int count(ll v) {
        if (!root)
            return 0;
        return root->count(v);
    }

    void ord() {
        root->ord();
        LOG("\n");
    }
};

const double ALPHA = 0.78;
const int P = 1e9;

int n, ql, qr;
ll ans;
int r[N], prt[N], sub[N], que[N];
ll divdis[N];
bool vis[N], cut[N];
int gdep[N];
ll gdis[N];
int gprt[N][LGN];
Edge* g[N];
Treap t[N], t2[N];
Treap save;
set<int> ch[N];
Treap::Node* Treap::Node::reuse[N * LGAN];
int Treap::Node::rcnt;

void addEdge(int u, int v, int w);
int lca(int u, int v);
ll dis(int u, int v);
int divide(int u);
void bfs(int u);

int main() {
//    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
    srand(time(NULL));
    int tc, ig;
    scanf("%d%d%d%d%d", &tc, &n, &ig, &ig, &r[1]);
    fill(cut + 1, cut + n + 1, true);
    puts("0");
    sub[1] = 1;
    t[1].insert(-r[1]);
    for (int u = 2; u <= n; ++u) {
        int v, w, xo = ans % P;
        scanf("%d%d%d", &v, &w, &r[u]);
        v ^= xo;
        prt[u] = v;
        addEdge(u, v, w);
        addEdge(v, u, w);
        ch[v].insert(u);
        gdep[u] = gdep[v] + 1;
        gdis[u] = gdis[v] + w;
        gprt[u][0] = v;
        for (int i = 1; i < LGN; ++i)
            gprt[u][i] = gprt[gprt[u][i - 1]][i - 1];
        for (int uu = u; uu; uu = prt[uu]) {
            ++sub[uu];
            ll k = r[u] - dis(u, uu);
            ans += t[uu].count(k);
            t[uu].insert(-k);
            if (prt[uu]) {
                ll k2 = r[u] - dis(u, prt[uu]);
                ans -= t2[uu].count(k2);
                t2[uu].insert(-k2);
            }
        }
        printf("%lld\n", ans);
        int scape = 0;
        for (int uu = u; prt[uu]; uu = prt[uu]) {
            if (sub[uu] >= sub[prt[uu]] * ALPHA)
                scape = prt[uu];
        }
        if (!scape)
            continue;
        int ori = u;
        LOG("SCAPE %d %d\n", scape, sub[scape]);
        int sprt = prt[scape];
        save.root = t2[scape].root;
        t2[scape].root = NULL;
        que[ql = 0] = scape;
        qr = 1;
        while (ql < qr) {
            u = que[ql++];
            cut[u] = false;
            for (set<int>::iterator it = ch[u].begin(); it != ch[u].end(); ++it)
                que[qr++] = *it;
            ch[u].clear();
            t[u].clear();
            t2[u].clear();
        }
        u = divide(scape);
        if (sprt) {
            prt[u] = sprt;
            ch[sprt].erase(scape);
            ch[sprt].insert(u);
            t2[u].root = save.root;
            save.root = NULL;
        }
        u = ori;
        fflush(stdout);
    }
    return 0;
}

inline void bfs(int u) {
    que[ql = 0] = u;
    qr = 1;
    while (ql < qr) {
        u = que[ql++];
        vis[u] = true;
        for (Edge* p = g[u]; p; p = p->next)
            if (!vis[p->v] && !cut[p->v])
                que[qr++] = p->v;
    }
}

int divide(int u) {
    static int mex[N];
    bfs(u);
    int div = que[qr - 1];
    for (int i = qr - 1; i >= 0; --i) {
        u = que[i];
        vis[u] = false;
        sub[u] = 1;
        mex[u] = 0;
        for (Edge* p = g[u]; p; p = p->next)
            if (!vis[p->v] && !cut[p->v]) {
                sub[u] += sub[p->v];
                mex[u] = max(mex[u], sub[p->v]);
            }
        mex[u] = max(mex[u], qr - sub[u]);
        if (mex[u] < mex[div])
            div = u;
    }
    cut[div] = true;
    sub[div] = qr;
    divdis[div] = 0;
    t[div].insert(-r[div]);
    for (Edge* p = g[div]; p; p = p->next)
        if (!cut[p->v]) {
            divdis[p->v] = p->w;
            bfs(p->v);
            Treap cur;
            cur.root = NULL;
            for (int i = 0; i < qr; ++i) {
                int v = que[i];
                vis[v] = false;
                t[div].insert(divdis[v] - r[v]);
                cur.insert(divdis[v] - r[v]);
                for (Edge* q = g[v]; q; q = q->next)
                    if(vis[q->v] && !cut[q->v])
                        divdis[q->v] = divdis[v] + q->w;
            }
            int vdiv = divide(p->v);
            ch[div].insert(vdiv);
            prt[vdiv] = div;
            t2[vdiv].root = cur.root;
            cur.root = NULL;
        }
    prt[div] = 0;
    return div;
}

inline void addEdge(int u, int v, int w) {
    static Edge pool[N * 2];
    static Edge* p = pool;
    p->v = v;
    p->w = w;
    p->next = g[u];
    g[u] = p;
    ++p;
}

inline int lca(int u, int v) {
    if (gdep[u] < gdep[v])
        swap(u, v);
    for (int i = LGN - 1; i >= 0; --i)
        if (gdep[u] - (1 << i) >= gdep[v])
            u = gprt[u][i];
    if (u == v)
        return u;
    for (int i = LGN - 1; i >= 0; --i)
        if (gprt[u][i] != gprt[v][i]) {
            u = gprt[u][i];
            v = gprt[v][i];
        }
    return gprt[u][0];
}

inline ll dis(int u, int v) {
    return gdis[u] + gdis[v] - 2 * gdis[lca(u, v)];
}