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
#include <bits/stdc++.h>

struct Droga{
    int cel;
    long long cena;
};

int target = -1;
long long result = 0;

void dfs(std::vector<Droga> tablica[], long long results[], long long ceny[], int current, int prev, long long koszty){
    //std::cout << "CURRENT: " << current << "\n";
    int next = -1;
    for (int i = 0; i < tablica[current].size(); i++){
        next = tablica[current][i].cel;
        if (next != prev){
            koszty += tablica[current][i].cena;
            results[next] = ceny[next] - koszty;
            if (results[next] >= result){
                result = results[next];
                target = next;
            }
            else if (results[next] == result){
                if (next < target)
                    target = next;
            }
            else if (target == -1){
                result = results[next];
                target = next;
            }
            dfs(tablica, results, ceny, next, current, koszty);
        }
    }
    return;
}

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);

    int n, q; // liczba miast, dni
    std::cin >> n >> q;
    long long ceny[100005];
    for (int i = 1; i <= n; i++)
        std::cin >> ceny[i];
    // graf
    std::vector <Droga> tablica[100006];
    int a, b;
    long long c;
    for (int i = 0; i < n-1; i++){
        std::cin >> a >> b >> c;
        Droga d1;
        d1.cel = b;
        d1.cena = c;
        tablica[a].push_back(d1);
        d1.cel = a;
        tablica[b].push_back(d1);
    }

    // zmiany
    int rodzaj;
    int x;
    long long v; // do zmiany zysku, target, cena;
    // a, b, c uzywane do zmiany krawedzi
    int current = 1;
    long long results[100005];
    long long koszty = 0;
    for (int i = 0; i < q; i++){
        std::cin >> rodzaj;
        if (rodzaj == 1){ // zmiana zysku
            std::cin >> x >> v;
            ceny[x] = v;
        }
        else if (rodzaj == 2){ // zmiana krawedzi
            std::cin >> a >> b >> c;
            for (int i = 0; i < tablica[a].size(); i++)
                if (tablica[a][i].cel == b)
                    tablica[a][i].cena = c;
            for (int i = 0; i < tablica[b].size(); i++)
                if (tablica[b][i].cel == a)
                    tablica[b][i].cena = c;
        }
        //results = new long long[n];
        koszty = 0;
        results[current] = 0;
        dfs(tablica, results, ceny, current, -1, koszty);
        std::cout << target << " ";     
        current = target;
        target = -1;
        result = 0;
    }
}