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
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll inf = 1e18;
const int roz = 1e5 + 10;

ll z[roz];
vector <pair <int, ll> > graf[roz];

ll odl[roz];
ll ost[roz];
int dfs(int a, int o)
{
    int i;
    for(i = 0; i < graf[a].size(); i++)
    {
        if(ost[graf[a][i].first] != 0)
        {
            odl[graf[a][i].first] = odl[a] + graf[a][i].second;
            ost[graf[a][i].first] = o;
            dfs(graf[a][i].first, o);
        }
    }
}

int main()
{
    int n, q, i, j;
    cin>>n>>q;

    for(i = 1; i <= n; i++)
    {
        cin>>z[i];
    }

    for(i = 1; i <= n - 1; i++)
    {
        int a, b;
        ll c;
        cin>>a>>b>>c;
        graf[a].push_back(make_pair(b, c));
        graf[b].push_back(make_pair(a, c));
    }

    int akt = 1;
    for(j = 1; j <= q; j++)
    {
        int r;
        cin>>r;
        if(r == 1)
        {
            int v; ll d;
            cin>>v>>d;
            z[v] = d;
        }
        else
        {
            int a, b; ll d;
            cin>>a>>b>>d;

            for(i = 0; i < graf[a].size(); i++)
            {
                if(graf[a][i].first == b)
                    graf[a][i] = make_pair(b, d);
            }
            for(i = 0; i < graf[b].size(); i++)
            {
                if(graf[b][i].first == a)
                    graf[b][i] = make_pair(a, d);
            }
        }

        ost[akt] = j;
        dfs(akt, j);

        ll maks = 0;
        int dok = 0;
        for(i = 1; i <= n; i++)
        {
            if(z[i] - odl[i] > maks)
            {
                dok = i;
                maks = z[i] - odl[i];
            }
        }
        akt = dok;
        cout<<akt<<" ";
    }
}