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

typedef long long ll;

ll inf;

vector<int> graf[100001];

ll ceny[100001];
map<pair<int, int>, ll> mapa;

pair<ll, int> dfs(int w, int ojc, ll odl)
{
    pair<ll, int> ret = {-inf, 1};
    if(ojc != -1)
        ret = {ceny[w]-odl, -w};
    for(int i=0;i<(int)graf[w].size();i++)
    {
        if(graf[w][i] == ojc)
            continue;
        ret = max(ret, dfs(graf[w][i], w, odl + mapa[{graf[w][i],w}]));
    }
    return ret;
}

int main()
{
    inf = ll(1e9) * ll(1e9);
    int n, q;
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++)
    {
        ll a;
        scanf("%lld",&a);
        ceny[i] = a;
    }
    for(int i=1;i<n;i++)
    {
        int a, b;
        ll c;
        scanf("%d%d%lld",&a,&b,&c);
        a--, b--;
        mapa[{a,b}] = c;
        mapa[{b,a}] = c;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    int city = 0;
    for(int i=0;i<q;i++)
    {
        int tmp;
        scanf("%d", &tmp);
        if(tmp == 1)
        {
            int m;
            ll a;
            scanf("%d%lld",&m,&a);
            m--;
            ceny[m] = a;
        }
        else
        {
            int a, b;
            ll v;
            scanf("%d%d%lld",&a,&b,&v);
            a--, b--;
            mapa[{a,b}] = v;
            mapa[{b,a}] = v;
        }
        city = -dfs(city, -1, 0).second;

        printf("%d ",city+1);
    }
}