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

using namespace std;

int n, m ,a , b, co, gdzie, zamien_a, zamien_b;
long long w[100000], najwiecej, ile, o_ile, na_co;
long long maks, wartosc;
int obecny = 1, wypisz;
int odw[100000];
vector<pair<int, long long> > c[100000];

void DFS( int v, int k )
{
    odw[v]++;
    if(v!= obecny){
    ile = w[v]-maks;
    if(ile > najwiecej || (ile == najwiecej && v < wypisz))
    {
        najwiecej = ile;
        wypisz = v;
    }
    //cout << v << "  " << ile << "  " << w[v] << "  " << maks <<  "\n";
    }
    for(int i = 0; i<c[v].size(); i++)
    {
        if( (v==zamien_a && c[v].at(i).first == zamien_b ) || (v == zamien_b && c[v].at(i).first == zamien_a) )
        {
            c[v].at(i).second = na_co;
        }
        if(odw[c[v].at(i).first] != k )
        {
            maks+=c[v].at(i).second;
            DFS(c[v].at(i).first, k);
            maks-=c[v].at(i).second;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i<=n; i++)
    {
        cin >> w[i];
    }
    for(int i = 1; i<n; i++)
    {
        cin >> a >> b >> wartosc;
        c[a].push_back(make_pair(b, wartosc) );
        c[b].push_back(make_pair(a, wartosc) );
    }
    for(int i = 1; i<=n; i++)
    {
        ile = -2000000000000000;
        najwiecej = -2000000000000000;
        cin >> co;
        if(co == 1)
        {
            cin >> gdzie >> o_ile;
            w[gdzie] = o_ile;
        }
        else
        {
            cin >> zamien_a >> zamien_b >> na_co;
        }
        DFS(obecny, i);
        cout << wypisz << " ";
        obecny = wypisz;
    }

}