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>
#define MAX 100001
using namespace std;

long long tab[MAX];
int odwiedzone[MAX];

vector< pair <int, long long > > graf[MAX];

int n, q, ostatni, niedostepny;
long long maksymalny, porownywalny;

void init();
bool dfsCondition(int kolejka);
void updatePath(int a);

int dfs(int indeks, int kolejka) {
    if(dfsCondition(kolejka)) {
        maksymalny = porownywalny + tab[kolejka];
        ostatni = kolejka;
    }
    for(int i = 0; i < graf[kolejka].size(); ++i) {
        if(odwiedzone[graf[kolejka][i].first] != indeks) {
             porownywalny -= graf[kolejka][i].second;
            odwiedzone[graf[kolejka][i].first] = indeks;
            dfs(indeks, graf[kolejka][i].first);
            porownywalny += graf[kolejka][i].second;
        }
    }
}

int main() {
    int k, a;
    cin >> n >> q;

    init();

    ostatni = 1;
    int indeks = 1;
    while(q--) {
        cin >> a;
        updatePath(a);

        maksymalny = -1000;
        porownywalny = 0;
        odwiedzone[ostatni] = indeks;
        niedostepny = ostatni;

        dfs(indeks, ostatni);

        indeks++;
        cout << ostatni << ' ';
    }
    puts("");
}

void init() {
    long long a, b, c;
    for(int i = 1; i <= n; i++) odwiedzone[i] = 0;
    for(int i = 1; i <= n; i++) cin >> tab[i];
    for(int i = 0; i < n-1; i++) {
        cin >> a >> b >> c;
        graf[a].push_back(make_pair(b, c));
        graf[b].push_back(make_pair(a, c));
    }

}
bool dfsCondition(int kolejka) {
    return kolejka != niedostepny && (porownywalny + tab[kolejka] > maksymalny || (porownywalny + tab[kolejka] == maksymalny && kolejka < ostatni));
}

void updatePath(int a) {
    long long b, c;

    if(a == 1) {
        cin >> b >> c;
        tab[b] = c;
    } else {
        cin >> a >> b >> c;
        for(int i = 0; i < graf[a].size(); ++i)
            if(graf[a][i].first == b) {
                graf[a][i].second = c;
                break;
            }

        for(int i = 0; i < graf[b].size(); ++i)
            if(graf[b][i].first == a) {
                graf[b][i].second = c;
                break;
            }
    }
}