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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q, a, b, t; ll c;
    cin >> n >> q;
    bool Vis[n+1]; ll Z[n+1]; vector < vector < pair <ll,int> > > Neigh(n+1);
    for(int i=1; i<=n; i++)
        cin >> Z[i];
    for(int h=0; h<n-1; h++){
        cin >> a >> b >> c;
        Neigh[a].push_back({c,b});
        Neigh[b].push_back({c,a});
    }
    int u=1;
    for(int h=0; h<q; h++){
        cin >> t;
        if(t==1){
            cin >> a >> c;
            Z[a]=c;
        }
        else {
            cin >> a >> b >> c;
            for(int i=0; i<Neigh[a].size(); i++)
                if(Neigh[a][i].second==b)
                    Neigh[a][i].first=c;
            for(int i=0; i<Neigh[b].size(); i++)
                if(Neigh[b][i].second==a)
                    Neigh[b][i].first=c;
        }

            for(int i=0; i<=n; i++)
                Vis[i]=false;
            ll profit=(-1)*((1ll)<<60); int v=u; pair <ll,int> r;
            priority_queue < pair <ll,int> , vector < pair <ll,int> > , greater < pair <ll,int> > > Q;
            Q.push({0,u});
            while(!Q.empty())
                {
                    r = Q.top();
                    Q.pop();
                    if(!Vis[r.second]){
                        Vis[r.second]=true;
                        if(r.second!=u && (Z[r.second]-r.first>profit || ((Z[r.second]-r.first)==profit && r.second<v))){
                            profit = Z[r.second]-r.first;
                            v = r.second;
                        }
                        for(pair <ll,int> s : Neigh[r.second])
                            if(!Vis[s.second])
                                Q.push({r.first+s.first,s.second});
                    }
                }
            u = v;
        cout << u << " ";
    }
    cout <<endl;
    return 0;
}