cp-problems

Kalaba

解説

Link-Cut Tree に max-index を載せると解けます．

#include <bits/stdc++.h>
using namespace std;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

struct mid {
    int c;
    int id;
    mid(int c_ = 0, int id_ = -1) : c(c_), id(id_) {}
    mid operator+(const mid &a) { return c > a.c ? mid(c, id) : mid(a.c, a.id); }
};

using ll = int;

struct link_cut_tree {
    struct node {
        node *pp, *lp, *rp;
        mid val, sum;
        bool rev;
        node(mid v = 0) : pp(nullptr), lp(nullptr), rp(nullptr), val(v), sum(v), rev(0) {}
        bool is_root() { return pp == nullptr or (pp->lp != this and pp->rp != this); }
    };
    void rotr(node *x) {
        node *q = x->pp, *r = q->pp;
        if (q->lp = x->rp; x->rp != nullptr) x->rp->pp = q;
        x->rp = q, q->pp = x;
        update(q), update(x);
        if (x->pp = r; r != nullptr) {
            if (r->lp == q) r->lp = x;
            if (r->rp == q) r->rp = x;
            update(r);
        }
    }
    void rotl(node *x) {
        node *q = x->pp, *r = q->pp;
        if (q->rp = x->lp; x->lp != nullptr) x->lp->pp = q;
        x->lp = q, q->pp = x;
        update(q), update(x);
        if (x->pp = r; r != nullptr) {
            if (r->lp == q) r->lp = x;
            if (r->rp == q) r->rp = x;
            update(r);
        }
    }
    void splay(node *x) {
        push(x);
        while (not x->is_root()) {
            node *q = x->pp;
            if (q->is_root()) {
                push(q), push(x);
                q->lp == x ? rotr(x) : rotl(x);
            } else {
                node *r = q->pp;
                push(r), push(q), push(x);
                if (r->lp == q) {
                    q->lp == x ? rotr(q) : rotl(x), rotr(x);
                } else {
                    q->rp == x ? rotl(q) : rotr(x), rotl(x);
                }
            }
        }
    }
    mid sum(node *x) { return x == nullptr ? 0 : x->sum; }
    node *update(node *x) {
        x->sum = sum(x->lp) + sum(x->rp) + x->val;
        return x;
    }
    void push(node *x) {
        if (x->rev) {
            swap(x->lp, x->rp);
            if (x->lp != nullptr) x->lp->rev = !x->lp->rev;
            if (x->rp != nullptr) x->rp->rev = !x->rp->rev;
            x->rev = false;
        }
    }
    void toggle(node *x) { x->rev = !x->rev, push(x); }
    node *expose(node *x) {
        node *rp = nullptr;
        for (node *p = x; p != nullptr; p = p->pp) splay(p), p->rp = rp, rp = p, update(p);
        splay(x);
        return rp;
    }
    void cut(node *c) {
        expose(c);
        node *p = c->lp;
        c->lp = p->pp = nullptr;
    }
    void cutb(node *u, node *v) { evert(u), cut(v); }
    void link(node *c, node *p) { expose(c), expose(p), c->pp = p, p->rp = c; }
    void linkb(node *u, node *v) { evert(u), evert(v), link(u, v); }
    void evert(node *x) { expose(x), toggle(x), push(x); }
    node *get_root(node *x) {
        expose(x);
        while (x->lp != nullptr) push(x), x = x->lp;
        splay(x);
        return x;
    }
    node *lca(node *u, node *v) {
        return get_root(u) == get_root(v) ? (expose(u), expose(v)) : nullptr;
    }
    mid path_sum(node *u, node *v) {
        evert(u), expose(v);
        return v->val + sum(v->lp);
    }
    node *update_val(node *x, mid val) {
        expose(x), x->val = val, splay(x);
        return x;
    }
    node *make_node(mid val = 0) { return new node(val); }
} lct;
typedef link_cut_tree::node NODE;
#define NIL() lct.make_node()
#define MAKE(a, b) lct.make_node(mid(a, b))
#define LINK(a, b) lct.linkb(v[a], v[b])
#define CUT(a, b) lct.cutb(v[a], v[b])
#define MAX(a, b) lct.path_sum(v[a], v[b])
#define UPDATE(a, b) lct.update_val(v[a], b)

signed main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int A[N - 1], B[N - 1], C[N - 1];

    vector<NODE *> v(N + N - 1);
    for (int i = 0; i < N; i++) v[i] = NIL();

    for (int i = 0; i < N - 1; ++i) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--, B[i]--;

        v[N + i] = MAKE(C[i], i);
        LINK(A[i], N + i);
        LINK(B[i], N + i);
    }

    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        mid x = MAX(a, b);
        if (c >= x.c) {
            cout << c << '\n';
        } else {
            cout << x.c << '\n';

            CUT(A[x.id], N + x.id);
            CUT(B[x.id], N + x.id);

            A[x.id] = a;
            B[x.id] = b;
            C[x.id] = c;

            LINK(A[x.id], N + x.id);
            LINK(B[x.id], N + x.id);

            UPDATE(N + x.id, mid(C[x.id], x.id));
        }
    }
}