1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
#include <bits/stdc++.h>
using namespace std;

using u64 = uint64_t;
using i64 = int64_t;
const i64 inf = (1ll << 62);
template <typename C> i64 isize(const C& c) { return static_cast<i64>(c.size()); }

// print tuples {{{
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& t) {
    return os << '[' << t.first << ',' << t.second << ']';
}
// }}}
// print containers {{{
template <typename It>
void print(ostream& os, It begin, It end, u64 len, u64 limit = 30) {
    u64 count = 0;
    os << "{";
    while (begin != end && count < limit) {
        os << "(" << *begin << ")";
        count++;
        begin++;
    }
    if (begin != end)
        os << "... " << len << " total";
    os << "}";
}
#define MAKE_PRINTER_1(container) \
template <typename T> ostream& operator<<(ostream& os, const container<T>& t) { print(os, t.begin(), t.end(), t.size()); return os; }
#define MAKE_PRINTER_2(container) \
template <typename T1, typename T2> \
ostream& operator<<(ostream& os, const container<T1, T2>& t) { \
    print(os, t.begin(), t.end(), t.size()); \
    return os; \
}
MAKE_PRINTER_1(vector)
MAKE_PRINTER_2(map)
MAKE_PRINTER_1(set)
MAKE_PRINTER_2(unordered_map)
MAKE_PRINTER_1(unordered_set)
#undef MAKE_PRINTER_1
#undef MAKE_PRINTER_2
// }}}
// read/write {{{
template <typename T> T read() { T e; cin >> e; return e; }
void read() {}
template <typename T, typename ...Ts> void read(T& v, Ts& ...ts) { v = read<T>(); read(ts...); }
template <typename T> vector<T> readv(u64 n) { vector<T> v; for (u64 i = 0; i < n; i++) v.push_back(read<T>()); return v; }
template <typename T> struct identity { const T& operator()(const T& t) const { return t; } };
#define PRINTERS(FNAME, OUTP) \
    template <typename T> void FNAME(const T& t) { OUTP << t << ' '; } \
    void FNAME##ln() { OUTP << '\n'; } \
    template <typename T> void FNAME##ln(const T& t) { OUTP << t << '\n'; } \
    template <typename T, typename F = identity<typename T::value_type>> \
    void FNAME##v(const T& t, F f = F()) { for (const auto& e : t) FNAME(f(e)); FNAME##ln(); }
PRINTERS(print, cout)
#ifdef DEBUG_PRINTS
    PRINTERS(dprint, cerr)
#else
# define dprint(...)
# define dprintv(...)
# define dprintln(...)
#endif
/// }}}

struct Node {
    i64 node_id; // my own index
    i64 parent_id; // -1 if root
    vector<i64> children;
    i64 city_rank;
    i64 city_cost;
    i64 tree_path_id;
    i64 index_in_tree_path;
    i64 height;
    friend ostream& operator<<(ostream& os, const Node& n) {
        os << "\n\nNode(";
        os << "\tnode_id=" << n.node_id << "\n";
        os << "\tparent_id=" << n.parent_id << "\n";
        os << "\tchildren=" << n.children << "\n";
        os << "\tcity_rank=" << n.city_rank << "\n";
        os << "\tcity_cost=" << n.city_cost << "\n";
        os << "\ttree_path_id=" << n.tree_path_id << "\n";
        os << "\tindex_in_tree_path=" << n.index_in_tree_path << "\n";
        os << "\theight=" << n.height << ")";
        return os;
    }
};
vector<Node> nodes_;

struct Deal {
    i64 who, deal;
    friend ostream& operator<<(ostream& os, const Deal& d) {
        return os << "Deal(who=" << d.who << ",deal=" << d.deal << ")";
    }
    bool operator<(const Deal& other) const { return (deal == other.deal) ? (who > other.who) : (deal < other.deal); }
};

struct TreePath;
TreePath& tp(i64 who);
Deal get_best_deal(i64 who);
i64 get_travel_cost(i64 who);
i64 get_parent_nodeid(i64 who);
Deal get_best_deal_for_node(i64 nodeid);


struct TreePath {
    TreePath(vector<i64> treenodes) : ts_(-1), treenodes_(treenodes)
    {}
    Deal get_best_deal(i64 who) const {
        dprint("get best deal for "); dprintln(who);
        Deal best_deal = get_best_deal_for_node(who);
        const auto idx = nodes_[who].index_in_tree_path;
        {
            i64 cost = 0;
            for (u64 i = idx + 1; i < treenodes_.size(); i++) {
                cost += nodes_[treenodes_[i]].city_cost;
                auto deal = get_best_deal_for_node(treenodes_[i]);
                deal.deal += cost;
                if (best_deal < deal)
                    best_deal = deal;
            }
        }
        {
            i64 cost = 0;
            for (i64 i = idx - 1; i >= 0; i--) {
                cost += nodes_[treenodes_[i + 1]].city_cost;
                auto deal = get_best_deal_for_node(treenodes_[i]);
                deal.deal += cost;
                if (best_deal < deal)
                    best_deal = deal;
            }
        }
        dprint("best deal for "); dprint(who); dprint(": "); dprintln(best_deal);
        return best_deal;
    }
    i64 get_parent_nodeid() const {
        assert(treenodes_.size());
        return nodes_[treenodes_[0]].parent_id;
    }
    i64 get_travel_cost(i64 who) const {
        i64 cost = 0;
        for (i64 i = 0; i <= nodes_[who].index_in_tree_path; i++)
            cost += nodes_[treenodes_[i]].city_cost;
        return cost;
    }
private:
    i64 ts_;
    vector<i64> treenodes_;
    friend ostream& operator<<(ostream& os, const TreePath& p) {
        os << "\n\nTreePath(\n";
        os << "\tts=" << p.ts_ << "\n";
        os << "\tnodes=" << p.treenodes_ << ")";
        return os;
    }
};
vector<TreePath> treepaths_;
TreePath& tp(i64 who) { return treepaths_[nodes_[who].tree_path_id]; }
Deal get_best_deal(i64 who) { return tp(who).get_best_deal(who); }
i64 get_travel_cost(i64 who) { return tp(who).get_travel_cost(who); }
i64 get_parent_nodeid(i64 who) { return tp(who).get_parent_nodeid(); }

// {{{ init tree
void init_parents_(const vector<vector<pair<i64, i64>>>& graph, i64 node_id, i64 parent_id) {
    auto& node = nodes_[node_id];
    node.node_id = node_id;
    node.height = 0;
    for (auto child_tuple : graph[node_id]) {
        const auto child_id = child_tuple.first;
        const auto child_cost = child_tuple.second;
        if (child_id == parent_id)
            continue;
        auto& child = nodes_[child_id];
        node.children.push_back(child_id);
        child.parent_id = node_id;
        child.city_cost = child_cost;
        init_parents_(graph, child_id, node_id);
        node.height = max(node.height, child.height + 1);
    }
}
void init_tree_paths_(Node& node, vector<i64>& tree_path) {
    node.index_in_tree_path = tree_path.size();
    tree_path.push_back(node.node_id);
    if (node.children.empty()) {
        for (auto node_id : tree_path) {
            auto tree_path_id = treepaths_.size();
            nodes_[node_id].tree_path_id = tree_path_id;
        }
        treepaths_.emplace_back(tree_path);
    } else {
        bool heavy_path_completed = false;
        for (auto child_id : node.children) {
            auto& child = nodes_[child_id];
            if (heavy_path_completed || node.height > child.height + 1) {
                vector<i64> new_tree_path;
                init_tree_paths_(child, new_tree_path);
            } else {
                init_tree_paths_(child, tree_path);
                heavy_path_completed = true;
            }
        }
    }
}
void init(const vector<vector<pair<i64, i64>>>& graph, const vector<i64>& ranks) {
    assert(nodes_.empty());
    assert(!graph.empty());
    nodes_.resize(graph.size());
    auto& root = nodes_[0];
    root.parent_id = -1;
    root.city_cost = -inf;
    for (i64 i = 0; i < isize(ranks); i++)
        nodes_[i].city_rank = ranks[i];
    init_parents_(graph, 0, -1);
    vector<i64> tree_path;
    init_tree_paths_(root, tree_path);
}
// }}}
Deal get_best_deal_for_node(i64 nodeid) {
    // brute force: check all children outside treenode_ - call get_best_deal for them
    // optimal: use priority_queue to store their results
    auto& node = nodes_[nodeid];
    Deal best_deal{nodeid, node.city_rank};
    for (const auto child_id: node.children) {
        auto& child = nodes_[child_id];
        if (child.tree_path_id == node.tree_path_id)
            continue;
        Deal new_deal = get_best_deal(child_id);
        new_deal.deal += nodes_[child_id].city_cost;
        if (best_deal < new_deal)
            best_deal = new_deal;
    }
    return best_deal;
}


i64 get_best_city(i64 from) {
    dprint("get best city: "); dprintln(from);
    Deal best_deal {from, -inf};
    i64 travel_cost = 0;
    while (from != -1) {
        auto local_best_deal = get_best_deal(from);
        local_best_deal.deal += travel_cost;
        if (best_deal < local_best_deal)
            best_deal = local_best_deal;
        travel_cost += get_travel_cost(from);
        from = get_parent_nodeid(from);
    }
    dprint("best deal: "); dprintln(best_deal);
    return best_deal.who;
}
void update_cost(i64 node1, i64 node2, i64 cost) {
    dprint("update cost: "); dprint(node1); dprint(node2); dprintln(cost);
    i64 who;
    if (nodes_[node1].parent_id == node2)
        who = node1;
    else if (nodes_[node2].parent_id == node1)
        who = node2;
    else
        assert(false);
    nodes_[who].city_cost = cost;
}
i64 update_gain(i64 who, i64 gain) {
    dprint("update gain: "); dprint(who); dprintln(gain);
    auto prev_gain = nodes_[who].city_rank;
    nodes_[who].city_rank = gain;
    return prev_gain;
}

// debug helper {{{
i64 max_height = 0;
i64 find_treepaths_height(i64 node_id = 0) {
    i64 current_height = 0;
    for (auto child_id : nodes_[node_id].children) {
        auto child_height = find_treepaths_height(child_id);
        if (nodes_[child_id].tree_path_id != nodes_[node_id].tree_path_id)
            current_height = max(current_height, child_height + 1);
    }
    max_height = max(max_height, current_height);
    return current_height;
}
// debug helper }}}

void go() {
    vector<vector<pair<i64, i64>>> g(read<u64>());
    const auto q = read<i64>();
    auto ranks = readv<i64>(g.size());
    for (u64 i = 1; i < g.size(); i++) {
        i64 a, b, c;
        read(a, b, c);
        a--;
        b--;
        c = -c;
        g[a].push_back(make_pair(b, c));
        g[b].push_back(make_pair(a, c));
    }
    init(g, ranks);
#ifdef DEBUG_PRINTS
    find_treepaths_height(0);   
    dprint("height: "); dprintln(max_height);
    dprint("paths:"); dprintln(treepaths_);
#endif
    i64 best_city = 0;
    for (i64 i = 0; i < q; i++) {
        auto t = read<i64>();
        if (t == 1) {
            i64 who, gain;
            read(who, gain);
            who--;
            update_gain(who, gain);
        } else if (t == 2) {
            i64 node1, node2, cost;
            read(node1, node2, cost);
            node1--;
            node2--;
            cost = -cost;
            update_cost(node1, node2, cost);
        } else {
            assert (false);
        }
        auto prev_best_city = best_city;
        auto prev_gain = update_gain(best_city, -inf);
        best_city = get_best_city(best_city);
        update_gain(prev_best_city, prev_gain);
        print(best_city + 1);
    }
    println();
}

int main () { // {{{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    go();
} //