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
#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

struct Edge {
    Edge(long long v1, long long v2) : v1(v1), v2(v2) {}
    long long v1, v2;
};

ostream &operator<<(ostream &s, const Edge &e) {
    return s << '(' << e.v1 << ", " << e.v2 << ')';
}

bool operator<(const Edge &e1, const Edge &e2) {
    if (e1.v1 != e2.v1) return e1.v1 < e2.v1;
    return e1.v2 < e2.v2;
}

struct NodeData {
    long long profit;
    vector<int> neighbours;
};

NodeData nodes[100003];
map<Edge, long long> edgeCosts;
int currentNode = 1;
int n, q;

long long profits[100003];
long long fakeProfit = 1ll << 62;

void bfs() {
    long long maxProfit = -fakeProfit;
    long long maxNode = currentNode;
    for (int i = 1; i <= n; ++i) {
        profits[i] = fakeProfit;
    }
    profits[currentNode] = nodes[currentNode].profit;
    queue<int> bfsQueue;
    bfsQueue.push(currentNode);
    while (not bfsQueue.empty()) {
        int cn = bfsQueue.front();
        // cerr << "current node: " << cn << endl;
        for (auto n : nodes[cn].neighbours) {
            if (profits[n] == fakeProfit) {
                profits[n] = profits[cn] - nodes[cn].profit - edgeCosts[{cn, n}] + nodes[n].profit;
                // cerr << "new profit for node " << n << " -> " << profits[n] << endl;
                if (maxProfit < profits[n] or maxProfit == profits[n] and maxNode > n) {
                    maxProfit = profits[n];
                    maxNode = n;
                    // cerr << "new max node " << n << ", with  profit: " << maxProfit << endl;
                }
                bfsQueue.push(n);
            }
        }
        bfsQueue.pop();
    }
    // cerr << "profits: "; 
    // for (int i = 1; i < n; ++i) {
        // cerr << profits[i] << ' ';
    // }
    // cerr << endl;
    currentNode = maxNode;
    cout << maxNode << ' ';
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> nodes[i].profit;
    }
    for (int i = 0; i < n - 1; ++i) {
        int v1, v2, val;
        cin >> v1 >> v2;
        cin >> val;
        edgeCosts[{v1, v2}] = val;
        edgeCosts[{v2, v1}] = val;
        // cerr << Edge{v1, v2} << ", " << val << endl;
        nodes[v1].neighbours.push_back(v2);
        nodes[v2].neighbours.push_back(v1);
    }
    // cerr << "edge costs: ";
    // for (auto &edge: edgeCosts) {
        // cerr << edge.first << " -> " << edge.second << ",  ";
    // }
    // cerr << endl << "city costs: ";
    // for (int i = 1; i <= n; ++i) {
        // cerr << nodes[i].profit << ' ';
    // }
    // cerr << endl;
    for (int i = 0; i < q; ++i) {
        int var;
        cin >> var;
        switch (var) {
            case 1:
                {
                    long long city;
                    cin >> city;
                    cin >> nodes[city].profit;
                    break;
                }
            case 2:
                {
                    long long v1, v2, cost;
                    cin >> v1 >> v2 >> cost;
                    edgeCosts[{v1, v2}] = cost;
                    edgeCosts[{v2, v1}] = cost;
                    break;
                }
        }
        // cerr << "edge costs: ";
        // for (auto &edge: edgeCosts) {
            // cerr << edge.first << " -> " << edge.second << ",  ";
        // }
        // cerr << endl << "city costs: ";
        // for (int i = 1; i <= n; ++i) {
            // cerr << nodes[i].profit << ' ';
        // }
        // cerr << endl;
        bfs();
    }
}