题解

（请在此补充题目的中文题解与思路描述。）

#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout)
#define ll long long
#define ld long double
#define il inline
#define pii pair <int, int>
#define pil pair <int, ll>
#define pli pair <ll, int>
#define fi first
#define se second
#define mid (l + r >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)
#define pb push_back
#define popc __builtin_popcount
#define inf 1000000000
#define pinf {(ll)(8e18), 0}
const int N = 1e5 + 5;
int n, m, cur = 1, dfn, L[N], R[N], de[N], fa[N][18]; ll _, a[N], b[N], t[N];
vector <pil> g[N];
void dfs(int u, int f)
{
    fa[u][0] = f; de[u] = de[f] + 1; L[u] = ++dfn;
    for (int h = 1; h <= 17; h++) fa[u][h] = fa[fa[u][h-1]][h-1];
    for (auto [v, w] : g[u]) if (v != f) b[v] = w, dfs(v, u);
    R[u] = dfn;
}
int lca(int u, int v)
{
    if (de[u] < de[v]) swap(u, v); int dc = de[u] - de[v];
    for (int i = 17; i >= 0; i--) if (dc >> i & 1) u = fa[u][i];
    if (u == v) return u;
    for (int i = 17; i >= 0; i--) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
void mdf(int l, int r, ll v)
{
    for (; l <= n; l += l & -l) t[l] += v;
    for (r++; r <= n; r += r & -r) t[r] -= v;
}
ll qry(int x) {ll s = 0; for (; x; x -= x & -x) s += t[x]; return s;}
ll dis(int u, int v) {return qry(L[u]) + qry(L[v]) - 2 * qry(L[lca(u,v)]);}
int q[N], h, fa2[N], sz[N], mx[N]; bool o[N]; vector <int> anc[N], sub[N];
int fnd(int rt)
{
    q[h=1] = rt;
    for (int i = 1; i <= h; i++)
    {
        int u = q[i]; sz[u] = 1; mx[u] = 0;
        for (auto [v, w] : g[u]) if (o[v] && v != fa2[u]) q[++h] = v, fa2[v] = u;
    }
    for (int i = h; i > 1; i--) 
    {
        int v = q[i], u = fa2[v];
        sz[u] += sz[v]; mx[u] = max(mx[u], sz[v]);
    }
    int ret = 0, mn = inf;
    for (int i = 1; i <= h; i++)
    {
        int u = q[i]; 
        if (sz[rt] - sz[u] > mx[u]) mx[u] = sz[rt] - sz[u];
        if (mx[u] < mn) mn = mx[u], ret = u;
    }
    return ret;
}
void dfz(int u, int f)
{
    int rt = fnd(u);
    q[h=1] = rt; fa2[rt] = o[rt] = 0;
    for (int i = 1; i <= h; i++)
    {
        int u = q[i];
        for (auto [v, w] : g[u]) if (o[v] && v != fa2[u]) q[++h] = v, fa2[v] = u;
    }
    for (int i = 1; i <= h; i++) anc[q[i]].pb(rt), sub[rt].pb(L[q[i]]);
    for (auto [v, w] : g[rt]) if (o[v]) dfz(v, rt);
}
int pos(vector <int>& o, int x) {return lower_bound(o.begin(), o.end(), x) - o.begin() + 1;}
struct sgt
{
    int n; vector <ll> tg; vector <pli> t1, t2;
    void crt(int _n) {n = _n; tg.resize(4 * n + 5); t1.resize(4 * n + 5); t2.resize(4 * n + 5);}
    void pu(int p)
    {
        if (t1[ls] < t1[rs]) t1[p] = t1[ls], t2[p] = min(t2[ls], t1[rs]);
        else t1[p] = t1[rs], t2[p] = min(t1[ls], t2[rs]);
    }
    void pt(int p, ll v) {tg[p] += v; t1[p].fi += v; t2[p].fi += v;}
    void pd(int p) {if (tg[p]) pt(ls, tg[p]), pt(rs, tg[p]), tg[p] = 0;}
    void mdf(int p, int l, int r, int a, pli v)
    {
        if (l == r) return t1[p] = v, t2[p] = pinf, void(); pd(p);
        if (a <= mid) mdf(ls, l, mid, a, v); else mdf(rs, mid + 1, r, a, v); pu(p);
    }
    void mdf(int p, int l, int r, int a, int b, ll v)
    {
        if (a > b) return; if (a <= l && r <= b) return pt(p, v); pd(p);
        if (a <= mid) mdf(ls, l, mid, a, b, v); if (b > mid) mdf(rs, mid + 1, r, a, b, v); pu(p);
    }
} T[N];
int main()
{
    // FILE("");
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) cin >> u >> v >> _, g[u].pb({v, _}), g[v].pb({u, _});
    dfs(1, 0); memset(o, 1, sizeof(o)); dfz(1, 0);
    for (int u = 1; u <= n; u++) mdf(L[u], R[u], b[u]), sort(sub[u].begin(), sub[u].end()), T[u].crt(sub[u].size());
    for (int u = 1; u <= n; u++) for (int v : anc[u]) T[v].mdf(1, 1, T[v].n, pos(sub[v], L[u]), {dis(u, v) - a[u], u});
    while (m--)
    {
        int op, x, y; ll w; pli ans = pinf;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> w; a[x] = w;
            for (int u : anc[x]) T[u].mdf(1, 1, T[u].n, pos(sub[u], L[x]), {dis(u, x) - a[x], x});
        }
        else 
        {
            cin >> x >> y >> w; if (de[x] > de[y]) swap(x, y); 
            int z = (anc[x].size() >= anc[y].size() ? x : y); 
            for (int u : anc[z])
            {
                if (L[y] <= L[u] && L[u] <= R[y]) 
                    T[u].mdf(1, 1, T[u].n, 1, pos(sub[u], L[y] + 1) - 1, w - b[y]), 
                    T[u].mdf(1, 1, T[u].n, pos(sub[u], R[y]), T[u].n, w - b[y]);
                else T[u].mdf(1, 1, T[u].n, pos(sub[u], L[y]), pos(sub[u], R[y] + 1) - 1, w - b[y]);
            }
			mdf(L[y], R[y], w - b[y]); b[y] = w;
		}
        for (int u : anc[cur]) 
        {
            pli ret = T[u].t1[1].se != cur ? T[u].t1[1] : T[u].t2[1];
            ret.fi += dis(cur, u); ans = min(ans, ret);
        }
        cout << (cur = ans.se) << " \n"[!T];
    }
    return 0;
}