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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
#include<ios>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<cmath>

#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

using namespace std;

int n,q;
int day;
/** Czy duże dane */
bool big;

class City;
class Road;
class Agglomeration;

/** Limit krawędzi dla jednego wierzchołka */
const int MAX_ROADS=25;

City *bestCity;
int64_t bestCost;

/**
 * Klasa określająca drogę, czyli krawędź
 */
class Road {
public:
    City *to;
    /** Koszt przejazdu */
    int64_t c;
public:
};

/** Identyfikator drogi dla mapy */
int64_t getRoadId(int a, int b) {
    if(a<b) return (((int64_t)a)<<32) | (int64_t)b;
    else return (((int64_t)b)<<32) | (int64_t)a;
}

class Agglomeration {
public:
    /** Licznik zmian dla danej aglomeracji */
    int change=0;
    /** Miasta wchodzące w skład aglomeracji, a później tylko miasta graniczne */
    vector<City*> cities;
public:
    void add(City* city);
    void merge(Agglomeration *o);
    void init();
    void updateHighways(City* to, int64_t change);
};

/** Licznik odwiedzonych miast sąsiednich algormeracji dla tego wyszukiwania */
int agSearchBC=0;

/**
 * Klasa określająca miastą, a więc wierzchołek w drzewie.
 */
class City {
public:
    /** Numer miasta */
    int nr;
    /** Zarobek dla danego miasta */
    int64_t z;
    /** Połaczenia wychodzące z danego miasta */
    vector<Road*> roads;
    /** Wierchołek bliżniaczy, w przypadk przekroczenia liczby krawędzi */
    City* split=NULL;
    /** Aglomeracja dla której należy to miasto */
    Agglomeration *ag;

    /** Ważność wierzchołka w kontekście algomeracji */
    int lastProcessed=-1;
    /** Drogi do innych aglomeracji z tego miasta */
    vector<Road*> highways;
    /** Maksymalny wynik dla tej aglomeracji dostępny z tego miasta */
    int64_t agBestCost;
    /** Nalepsze miasto dla tej aglomeracji dostępny z tego miasta */
    City* agBest;
private:
    City *addRoad(Road* road) {
        if(split==NULL) {
            if(roads.size()<MAX_ROADS) {
                roads.push_back(road);
                return this;
            } // do tego można jeszcze dodawać drogi
            split=new City();
            split->z=0;
            split->nr=-nr;  //??
            Road* r1=new Road();
            r1->to=split; r1->c=0;
            roads.push_back(r1);
            Road* r2=new Road();
            r2->to=this; r2->c=0;
            split->roads.push_back(r2);
        } else if(split->roads.size()>=MAX_ROADS) {
            City *n=new City();
            n->z=0;
            n->nr=-nr;

            Road *r1=new Road();
            r1->to=n; r1->c=0;
            split->roads.push_back(r1);
            Road *r2=new Road();
            r2->to=split; r2->c=0;
            n->roads.push_back(r2);

            split=n;
        }
        split->roads.push_back(road);
        return split;
    }
public:
    City() { }

    /** Dodanie połączenia pomiędzy dwoma miastami */
    void connect(Road* r1, Road* r2, City *to) {
        City* c1=addRoad(r1);
        City* c2=to->addRoad(r2);
        r1->to=c2;
        r2->to=c1;
    }

    /** Czy miasto graniczne */
    bool isBorderCity() {
        for(auto i = roads.begin();i!=roads.end();++i) {
            if((*i)->to->ag!=ag) return true;
        }
        return false;
    }

    /**
     * Pomocnicza funkcja sprawdzająca czy dana pozycja jest najlepsza
     */
    void checkCost(int64_t currentCost) {
        int64_t thisCost=currentCost+z;
        if(thisCost>=bestCost) {
            if(thisCost==bestCost) {
                if(bestCity->nr>nr) {
                    bestCity=this;
                }
            } else {
                bestCity = this;
                bestCost = thisCost;
            }
        }
    }

    /** Szukanie w grafie elementu z najmnieszym kosztem - przejście wszystkiego w głąb */
    void findRec(City* from, int64_t currentCost) {
        if(z>0) checkCost(currentCost); // pomijamy pomocnicze wierzchołki (miasta)

        for(vector<Road*>::iterator i=roads.begin();i!=roads.end();++i) {
            City* to=(*i)->to;
            if(to==from) continue;
            to->findRec(this, currentCost-(*i)->c);
        }

    }

    void rebuildBorderCityData(City* root, City* from, int64_t currentCost) {
        if(z>0) {
            int64_t thisCost=currentCost+z;
            if(thisCost>=root->agBestCost) {
                if(thisCost==root->agBestCost) {
                    if(root->agBest->nr > nr) {
                        root->agBest=this;
                    }
                } else {
                    root->agBest=this;
                    root->agBestCost=thisCost;
                }
            }
        }

        for(vector<Road*>::iterator i=roads.begin();i!=roads.end();++i) {
            City* to=(*i)->to;
            if(to==from) continue;
            if(ag==to->ag) {    // ta sama aglomeracja, to rekurencyjnie
                to->rebuildBorderCityData(root, this, currentCost - (*i)->c);
            } else {    // inna aglomeracja, to tylko zapisujemy koszt dojazdu do miasta w nowej aglomeracji
                Road* hw;
                if(agSearchBC<root->highways.size()) hw=root->highways[agSearchBC];
                else {  // przy pierwszym przejścu dodajemy drogi
                    hw=new Road();
                    hw->to=to;
                    root->highways.push_back(hw);
                }
                hw->c=-currentCost + (*i)->c;
                ++agSearchBC;
            }
        }
    }

    /** Dla miasta granicznego sprawdzenie, nalepszego wyniku w aglomeracji */
    void checkAgglomerationMax(int64_t currentCost) {
        if(lastProcessed!=ag->change || agBest==NULL) { // dane nieaktualne, należy odbudować
            agBestCost=numeric_limits<int64_t>::min();
            agBest=NULL;
            agSearchBC=0;

            rebuildBorderCityData(this, NULL, 0);
            lastProcessed=ag->change;
        }
        int64_t thisBest=agBestCost+currentCost;
        if(thisBest>=bestCost) {
            if(thisBest==bestCost) {
                if(bestCity->nr > agBest->nr) {
                    bestCity=agBest;
                }
            } else {
                bestCity=agBest;
                bestCost=thisBest;
            }
        }
    }

    /**
     * Metoda działająca na poziomie aglomeracji
     */
    void findGlobal(Agglomeration* from, int64_t currentCost) {
        checkAgglomerationMax(currentCost);
        for(vector<Road*>::iterator i=highways.begin();i!=highways.end();++i) {
            City* to=(*i)->to;
            if(to->ag==from) continue;
            to->findGlobal(ag, currentCost-(*i)->c);
        }
    }

    /** Etap lokalny poszukiwań - wewnątrz aglomeracji */
    void find(City* from, int64_t currentCost) {
        if(z>0) checkCost(currentCost);

        for(vector<Road*>::iterator i=roads.begin();i!=roads.end();++i) {
            City* to=(*i)->to;
            if(to==from) continue;
            if(ag!=to->ag) {    // jeżeli droga poza aglomerację, to przechodzimy na przeszukiwanie między aglomeracyjne
                to->findGlobal(ag, currentCost-(*i)->c);
            } else {    // wewnątrz tej aglomeracji, to normalne przeszukiwanie
                to->find(this, currentCost-(*i)->c);
            }
        }
    }

};

City cities[100000];
Road roads[200000]; // bo tam i z powrotem

map<int64_t, pair<Road*, Road*>> roadMap;

/** Aktualne miasto w którym się znajdujemy */
City* now;

/**
 * Aktualizacja ceny sprzedaży dla danego miasta i kwoty
 */
void updateCitySellings(int ci, int64_t z) {
    City* c=&cities[ci];
    /** Zmiana ceny */
    int64_t diff=z-c->z;
    if(diff==0) return;// brak zmiany

    c->z=z;
    if(!big) return;
    Agglomeration* ag=c->ag;

//    ag->change++; // aglomeracja traci wazność
    for(auto i = ag->cities.begin(); i!=ag->cities.end();++i) {
        City* bc=(*i);
        if(diff>0) {    // jeżeli jest wzrost zarobku
            if(bc->agBest==c) { // i jest to te miast, to bez sprawdzania wyjście po prostu więcej
                bc->agBestCost+=diff;
            } else bc->agBest=NULL; // traci ważność
        } else {    // spaden ceny
            if(bc->agBest!=c) { // jeżeli spadek ceny w innym miejście niż maksimum, to nie wpływa to na wynik
            } else {
                bc->agBest=NULL;    // jest to było maksium, to coś innego może stać się maksimum
            }
        }
    }
}

/**
 * Aktualizacja kosztu przejazdu daną drogą.
 */
void updateRoad(int a, int b, int64_t c) {
    pair<Road*,Road*> r=roadMap[getRoadId(a,b)];
    /** Zmiana kosztu przejazdu na danej drodze */
    int64_t diff=c - r.first->c;
    if(diff==0)return;

    r.first->c=c;
    r.second->c=c;
    if(!big) return;

    if(r.first->to->ag == r.second->to->ag) {// czy droga wewnątrz aglomeracji
        r.first->to->ag->change++; // jeżeli tak, to dane tracą ważność, bo wpływa to na wyszystkie wyniki
    } else { // jeżeli pomiędzy algomeracjami
        r.first->to->ag->updateHighways(r.second->to, diff);
        r.second->to->ag->updateHighways(r.first->to, diff);
    }
}

/**
 * Główna funkcja znajdująca kolejne miasto, do którego warto pojechać.
 */
int process() {
    // szukamy z tego miejsca przejścia do innego miasta, dla którego osiągniemy największy zysk możliwy
    bestCity=NULL;
    bestCost=numeric_limits<int64_t>::min()+1;

    int64_t tmp=now->z;
    now->z=-1;
    now->findRec(NULL, 0);
    now->z=tmp;
    now=bestCity;
    return bestCity->nr;
}

int processBig() {
    bestCity=NULL;
    bestCost=numeric_limits<int64_t>::min()+1;

    int64_t tmp=now->z;
    now->z=-1;
    now->find(NULL, 0);
    now->z=tmp;
    now=bestCity;
    return bestCity->nr;
}


void Agglomeration::add(City *city) {
    cities.push_back(city);
    city->ag=this;
}

void Agglomeration::merge(Agglomeration *o) {
    for(int i=0;i<o->cities.size();++i) {
        cities.push_back(o->cities[i]);
        o->cities[i]->ag=this;
    }
    o->cities.clear();
}

void Agglomeration::init() {
    change=0;
    // usuwamy informacje o miastach, które nie są graniczne
    for(int i=0;i<cities.size();++i) {
        if(!cities[i]->isBorderCity()) {
            cities[i]=cities[cities.size()-1];
            cities.erase(cities.end()-1);
        }
    }
}

void Agglomeration::updateHighways(City* to, int64_t change) {
    for(auto i=cities.begin();i!=cities.end();++i) {
        City *c=(*i);
        for(auto ri = c->highways.begin();ri!=c->highways.end();++ri) {
            Road* r=(*ri);
            if(r->to==to) r->c+=change;
        }
    }
}

class AgglomerationComparator {
public:
    bool operator() (Agglomeration* a, Agglomeration *b) {
        return a->change > b->change;
    }
};

int ac=0;
void buildAgglomerationsRec(City* from, Agglomeration* ag, City* c) {
    if (c->ag == NULL) {
        Agglomeration *sm = NULL;

        for (auto i = c->roads.begin(); i != c->roads.end(); ++i) {
            City *to = (*i)->to;
            if (to->ag == NULL) { // to mamy jakiś wierzchołek i robimy aglomeracje rozmiaru 2
                ag[ac].add(c);
                ag[ac].add(to);
                ++ac;
                break;
            } else {
                if (sm == NULL || sm->cities.size() > to->ag->cities.size()) sm = to->ag;  // minmalna aglomeracja
            }
        }
        if (c->ag == NULL) sm->add(c);
    }

    for (auto i = c->roads.begin(); i != c->roads.end(); ++i) {
        City *to = (*i)->to;
        if (to== from) continue;
        buildAgglomerationsRec(c, ag, to);
    }
}

void buildAgglomerations() {
    Agglomeration* ag=new Agglomeration[n+1];
    // tworzymy na początku algomeracje o rozmiarach 2 wierzchołków
    buildAgglomerationsRec(NULL, ag, &cities[0]);

    // po przejściu powyższego mamy aglomeracje o rozmiarze 2 lub większe
    priority_queue<Agglomeration*, vector<Agglomeration*>, AgglomerationComparator> queue;
    for(int i=0;i<ac;++i) {
        ag[i].change=ag[i].cities.size();
        queue.push(&ag[i]);
    }
    int limit=(int)(sqrt(n)*2.0);
    // bierzemy najmniejsze aglomeracje i łączymi z innymi małymi budując w ten sposób większe
    while(queue.size()>limit) {
        Agglomeration *i=queue.top(); queue.pop();
        if(i->change!=i->cities.size()) {       // czy wartość uległa zmianie?
            i->change=i->cities.size(); queue.push(i);  // wrzucamy z powrotem z właściwą wartością
            continue;
        }
        Agglomeration *sm=NULL;
        // szukamy najmniejszej sąsiedniej aglomeracji i się łączymy
        for(vector<City*>::iterator ci=i->cities.begin();ci!=i->cities.end();++ci) {
            City* c=(*ci);
            for(vector<Road*>::iterator ri=c->roads.begin();ri!=c->roads.end();++ri) {
                City* to=(*ri)->to;
                if(to->ag==i) continue;
                if(sm==NULL || sm->cities.size()>to->ag->cities.size()) sm=to->ag;
            }
        }
        sm->merge(i);
        // 'i' nie jest już wrzucany do kolejki, bo został przejęty
    }
    // na koniec inicjujemy dane w aglomeracjach
    while(queue.size()>0) {
        queue.top()->init();
        queue.pop();
    }
}

int main(int argc, char** argv) {
    // przyspiszenie cin/cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

//    std::ifstream in("tst5/tst_455_4_455.in");
//    std::cin.rdbuf(in.rdbuf());

    // wczytujemy dane
    cin>>n>>q;
    for(int i=0;i<n;++i) {
        cities[i].nr=i+1;
        cin>>cities[i].z;
    }  // wartości startowe

    int e=0;
    for(int i=1;i<n;++i) {  // krawędzie
        int a,b;
        cin>>a>>b;
        Road* r1=&roads[e++];
        Road* r2=&roads[e++];
        cin>>r1->c;
        r2->c=r1->c;
        cities[a-1].connect(r1, r2, &cities[b-1]);
        roadMap.insert(make_pair(getRoadId(a-1,b-1), make_pair(r1,r2)));
    }
    now=&cities[0];
    // budowanie aglomeracji
    big=((int64_t)n*(int64_t)q)>10000000;
//    big=true;
    if(big) buildAgglomerations();

    // zadania
    for(int i=0;i<q;++i) {
        int type;
        cin>>type;
        day=i+1;
        if(type==1) {   // sprzedaż
            int c;
            int64_t z;
            cin>>c>>z;
            updateCitySellings(c-1, z);
        } else {    // droga
            int a, b;
            int64_t c;
            cin>>a>>b>>c;
            updateRoad(a-1, b-1, c);
        }
        int res;
        if(big) res=processBig();
        else res=process();  // przetworzenie dnia
        cout<<res<<" ";
    }
    cout<<endl;

    return 0;
}