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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//
//  ban.cpp
//  
//
//  Created by Michał Buda on 25.11.2017.
//

#include <stdio.h>
#include <list>

struct PathInfo {
    int city;  // end city
    long long cost; // cost of path
};

int main() {
    int n; // number of cities
    int q; // number of days
    scanf("%d", &n);
    scanf("%d", &q);
    
    long long* prices = new long long[n]; //city prices
    bool* visited = new bool[n];
    long long* travel_cost = new long long[n];
    std::list<PathInfo>* graph = new std::list<PathInfo>[n];
    std::list<int> queue;
    
    for(int i = 0; i < n; ++i) {
        scanf("%lld", &prices[i]);
    }
    
    int a,b;
    long long p;
    for(int i = 0; i < n - 1; ++i) {
        scanf("%d", &a);
        scanf("%d", &b);
        scanf("%lld", &p);
        --a;
        --b;
        PathInfo a_pi, b_pi;
        a_pi.city = b;
        a_pi.cost = p;
        b_pi.city = a;
        b_pi.cost = p;
        graph[a].push_back(a_pi);  // a -> b
        graph[b].push_back(b_pi);  // b -> a
    }
    
    ////////////////
    
    int curr = 0;  //current city
    int u,v,t;
    int best_city;
    long long profit, max_profit;
    std::list<PathInfo>::iterator it;
    
    for(int d = 0; d < q; ++d) {
        scanf("%d", &t);
        if (t == 1) {
            scanf("%d", &a);  //city
            --a;
            scanf("%lld", &prices[a]);  //price, change banana price
        } else {
            scanf("%d", &a);  //city a
            scanf("%d", &b);  //city b
            scanf("%lld", &p); //price
            --a;
            --b;
            
            for (it = graph[a].begin(); it != graph[a].end(); ++it) {
                if(it->city == b) {
                    it->cost = p;
                    break;
                }
            }
            
            for (it = graph[b].begin(); it != graph[b].end(); ++it) {
                if(it->city == a) {
                    it->cost = p;
                    break;
                }
            }
        }
        
        best_city = -1;
        max_profit = -1;
        for (int i = 0; i < n; ++i) {
            travel_cost[i] = 0;
            visited[i] = false;
        }
        
        queue.push_back(curr);
        while (!queue.empty()) {
            u = queue.front();
            queue.pop_front();
            for (it = graph[u].begin(); it != graph[u].end(); ++it) {
                v = it->city;
                if(!visited[v]) { //not visited
                    if (u == curr) {
                        travel_cost[v] = it->cost;
                    } else {
                        travel_cost[v] = travel_cost[u] + it->cost;
                    }
                    profit = prices[v] - travel_cost[v];
                    if (best_city == -1) {
                        max_profit = profit;
                        best_city = v;
                    } else if (profit > max_profit) {
                        max_profit = profit;
                        best_city = v;
                    } else if (profit == max_profit) {
                        if (v < best_city) {
                            best_city = v;
                        }
                    }
                    queue.push_back(v);
                }
            }
            visited[u] = true;
        }
        printf("%d ", best_city + 1);
        curr = best_city;
    }
    delete [] prices;
    delete [] visited;
    delete [] travel_cost;
    delete [] graph;
    
    return 0;
}