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
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=1e5+5;
const long long INF=4*1e18;
int n, q, a, b, maks2;
long long val[N], c, way, maks;
vector<int> v[N];
vector<long long> u[N];
void dfs(int x, int popx)
{
        for(int i=0;i<v[x].size();i++)
        {
                int y=v[x][i];
                long long w=u[x][i];
                if(y!=popx)
                {
                        way+=w;
                        if(maks<val[y]-way)
                        {
                                maks=val[y]-way;
                                maks2=y;
                        }
                        else if(maks==val[y]-way) maks2=min(maks2,y);
                        dfs(y,x);
                        way-=w;
                }
        }
}
int main()
{
        scanf("%d%d", &n, &q);
        for(int i=1;i<=n;i++) scanf("%lld", &val[i]);
        for(int i=1;i<n;i++)
        {
                scanf("%d%d%lld", &a, &b, &c);
                v[a].push_back(b);
                v[b].push_back(a);
                u[a].push_back(c);
                u[b].push_back(c);
        }
        int ost=1;
        while(q--)
        {
                scanf("%d", &a);
                if(a==1)
                {
                        scanf("%d%lld", &a, &c);
                        val[a]=c;
                }
                else
                {
                        scanf("%d%d%lld", &a, &b, &c);
                        for(int i=0;i<v[a].size();i++)
                        if(v[a][i]==b) u[a][i]=c;
                        for(int i=0;i<v[b].size();i++)
                        if(v[b][i]==a) u[b][i]=c;
                }
                maks=-INF;
                dfs(ost,0);
  ost=maks2;
                printf("%d ", ost);
        }
        return 0;
}