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
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <functional>

#define D(x)
//#define MASK 100//131072
#define MASK 131072

using namespace std;

typedef long long I;

I duzo = 1LL<<61;

#define MAX (4*MASK)

int n,q,t=0;
map<int, I> E[MAX];
pair<int, I> cache[MAX][2];
int cachef[MAX][2];


pair<int, I> getOpt(int b,int a) {
    I maxC = -duzo;
    int maxV = b;
    D(cout << "getOpt: " << a << "->" << b <<"\n");
    if(a<=0) throw "1";

    if(cachef[b][0] == a) {
        D(cout << "cache0\n");
        return cache[b][0];
    }
    if(cachef[b][1] == a) {
        D(cout << "cache1\n");
        swap(cachef[b][1], cachef[b][0]);
        swap(cache[b][1], cache[b][0]);
        return cache[b][0];
    }

    for(auto &it: E[b]) {
        auto v = it.first;
        auto c = it.second;
        if(v==a) continue;
        auto o = getOpt(v,b);
        c+=o.second;
        if((c==maxC && maxV > o.first) || c>maxC) {
            maxC = c;
            maxV = o.first;
        }
    }
    swap(cachef[b][1], cachef[b][0]);
    swap(cache[b][1], cache[b][0]);
    auto w = make_pair(maxV, maxC);
    cachef[b][0] = a;
    cache[b][0] = w;
    D(cout << "add: " << a << "->" << b << " (" <<w.first << "," << w.second << ")\n");
    return w;
}

void remove_cache(int b) {

    if(b==0) return;
    D(cout << "remove: " <<"  ->"<< b << "\n");

    D(cout << "remove2: " <<cachef[b][1] << "->"<< b << " (" <<cache[b][1].first << "," << cache[b][1].second << ")\n");
    D(cout << "remove3: " <<cachef[b][0] << "->"<< b << " (" <<cache[b][0].first << "," << cache[b][0].second << ")\n");

    auto cf0 = cachef[b][0];
    auto cf1 = cachef[b][1];

    cachef[b][0] = 0;
    cachef[b][1] = 0;

    remove_cache(cf1);
    remove_cache(cf0);
}

void add(int a, int b, I v) {
    E[a].insert(make_pair(b, v));
}

void update(int a, int b, I v) {
    D(cout << "update:" << a << "->" << b << " - " << v << "\n");
    auto it = E[a].find(b);
    E[a].erase(it);
    add(a,b,v);
    remove_cache(a);
    remove_cache(b);
}


int main()
{
    I a,b,c,d,v;
    scanf("%d %d", &n, &q);
    for(int i=1;i<=n;i++) {
        scanf("%lld", &a);
        add(i,i+MASK, a);
        add(i+MASK,i, 0);
    }
    for(int i=1;i<n;i++) {
        scanf("%lld %lld %lld", &a, &b, &c);
        add(a,b, -c);
        add(b,a, -c);
    }

    int pos = 1+MASK;

    for(t=1;t<=q;t++) {
        scanf("%lld", &c);
        if(c == 1) {
            I i;
            scanf("%lld %lld", &i, &a);
            update(i,i+MASK, a);
        } else {
            scanf("%lld %lld %lld", &a, &b, &c);
            update(a,b, -c);
            update(b,a, -c);
        }
        auto o = getOpt(pos, pos);
        pos = o.first;
//        printf("%d\n", pos-MASK);
        printf("%d ", pos-MASK);
    }
//    cout << log << "\n";
}