[PA 2017] Banany

#include <cstdio>
#include <cstring>

#include <algorithm>

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

typedef long long ll;

struct data {
    ll s;
    int id;

    data() {}

    data(ll s, int id) : s(s), id(id) {}

    bool operator<(const data& x) const { return s < x.s || (s == x.s && id > x.id); }

    data operator+(ll x) const { return data(s + x, id); }

    data operator+=(ll x) { s += x; return *this; }
};

struct node {
    data d;
    ll lazy;
    int l, r;
    node *ls, *rs;

    void push_down();
    data get_d() const;
    data query(int l, int r);
    void change(int l, int r, ll x);
};

struct edge {
    int v;
    ll w;
    edge* next;
};

const int N = 100010, LGN = 20;
const ll INF = 1LL << 62;
const data DINF(-INF, 1 << 30);

int tm;
bool vis[N], cut[N];
int son[N], minmax[N], maxson[N], rid[N], cnt[N];
ll z[N], dis[N], ox[N];
edge* g[N];
node *xseg[N];
int rt[N][LGN], tlv[N][LGN], trv[N][LGN], prt[N][LGN];
ll pw[N][LGN];

void add_edge(int u, int v, ll w);
void divide(int u, int n);
void dfs(int u, int n);
void dfs2(int crt, int u);
node* create(int l, int r);

int main() {
//  freopen("test.out", "w", stdout);
//  freopen("test.err", "w", stderr);
    int n, q, s = 1;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &z[i]);
    for (int rep = 1; rep < n; ++rep) {
        int u, v;
        ll w;
        scanf("%d%d%lld", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    divide(1, n);
    while (q--) {
        int opt, u;
        scanf("%d%d", &opt, &u);
        if (opt == 1) {
            ll zi, delt;
            scanf("%lld", &zi);
            delt = zi - z[u];
            z[u] = zi;
            for (int i = 0; i < cnt[u]; ++i) {
                LOG("CHANGE %d\n", tlv[u][i]);
                xseg[rt[u][i]]->change(tlv[u][i], tlv[u][i], delt);
            }
        } else {
            int v;
            ll w;
            scanf("%d%lld", &v, &w);
            for (int i = 0; i < cnt[u]; ++i)
                if (prt[u][i] == v) {
                    ll delt = w - pw[u][i];
                    pw[u][i] = w;
                    xseg[rt[u][i]]->change(tlv[u][i], trv[u][i], -delt);
                }
            std::swap(u, v);
            for (int i = 0; i < cnt[u]; ++i)
                if (prt[u][i] == v) {
                    ll delt = w - pw[u][i];
                    pw[u][i] = w;
                    xseg[rt[u][i]]->change(tlv[u][i], trv[u][i], -delt);
                }
        }
        data ans(DINF);
        for (int i = 0; i < cnt[s]; ++i) {
            ans = std::max(ans, std::max(xseg[rt[s][i]]->query(1, tlv[s][i] - 1), xseg[rt[s][i]]->query(tlv[s][i] + 1, xseg[rt[s][i]]->r)) + xseg[rt[s][i]]->query(tlv[s][i], tlv[s][i]).s);
            LOG("%d: %lld\n", ans.id, ans.s - z[s]);
            LOG("%d\n", tlv[s][i]);
        }
        s = ans.id;
        if (q)
            printf("%d ", s);
        else
            printf("%d\n", s);
    }
    for (int i = 1; i <= n; ++i)
        LOG("%d\n", cnt[i]);
    return 0;
}

void divide(int u, int n) {
    dfs(u, n);
    u = minmax[u];
    LOG("DIVIDE %d %d %d\n", u, son[u], n);
    tm = 0;
    cut[u] = true;
    dis[u] = 0;
    dfs2(u, u);
    xseg[u] = create(1, n);
    for (edge* p = g[u]; p; p = p->next)
        if (!cut[p->v])
            divide(p->v, son[p->v]);
}

void dfs2(int crt, int u) {
    vis[u] = true;
    ++tm;
    int c = cnt[u];
    if (++cnt[u] >= LGN)
        exit(0);
    rt[u][c] = crt;
    tlv[u][c] = tm;
    ox[tm] = z[u] - dis[u];
    rid[tm] = u;
    son[u] = 1;
    for (edge* p = g[u]; p; p = p->next)
        if (!vis[p->v] && !cut[p->v]) {
            dis[p->v] = dis[u] + p->w;
            prt[p->v][c] = u;
            pw[p->v][c] = p->w;
            LOG("%d->%d\n", u, p->v);
            dfs2(crt, p->v);
            son[u] += son[p->v];
        }
    trv[u][c] = tm;
    vis[u] = false;
}

void dfs(int u, int n) {
    vis[u] = true;
    son[u] = 1;
    maxson[u] = 0;
    for (edge* p = g[u]; p; p = p->next)
        if (!vis[p->v] && !cut[p->v]) {
            dfs(p->v, n);
            son[u] += son[p->v];
            maxson[u] = std::max(maxson[u], son[p->v]);
        }
    minmax[u] = u;
    for (edge* p = g[u]; p; p = p->next)
        if (!vis[p->v] && !cut[p->v] && std::max(maxson[minmax[u]], n - son[minmax[u]]) > std::max(maxson[minmax[p->v]], n - son[minmax[p->v]]))
            minmax[u] = minmax[p->v];
    vis[u] = false;
}

node* create(int l, int r) {
    static node pool[N * LGN * 2];
    static node* top = pool;
    node* p = top;
    ++top;
    p->l = l;
    p->r = r;
    if (l == r) {
        p->d = data(ox[l], rid[l]);
        return p;
    }
    int mid = (l + r) >> 1;
    p->ls = create(l, mid);
    p->rs = create(mid + 1, r);
    p->d = std::max(p->ls->d, p->rs->d);
    return p;
}

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

void node::push_down() {
    if (!lazy)
        return;
    d += lazy;
    ls->lazy += lazy;
    rs->lazy += lazy;
    lazy = 0;
}

void node::change(int l, int r, ll x) {
    if (this->l == l && this->r == r) {
        lazy += x;
        return;
    }
    push_down();
    if (r <= ls->r)
        ls->change(l, r, x);
    else if (l >= rs->l)
        rs->change(l, r, x);
    else {
        ls->change(l, ls->r, x);
        rs->change(rs->l, r, x);
    }
    d = std::max(ls->get_d(), rs->get_d());
}

data node::query(int l, int r) {
    if (l > r)
        return DINF;
    if (this->l == l && this->r == r)
        return get_d();
    push_down();
    if (r <= ls->r)
        return ls->query(l, r);
    if (l >= rs->l)
        return rs->query(l, r);
    return std::max(ls->query(l, ls->r), rs->query(rs->l, r));
}

data node::get_d() const {
    return d + lazy;
}