Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
#include<cstdio>
#include <list>

#define N 100000

using namespace std;

long long int miasta[N + 10];

struct krawedz {
	long long int wierzcholek;
	long long int koszt;
};

list<krawedz> sasiedzi[N + 10];

long long int max_zysk;
long long int max_wierzcholek;

long long int czy_odwiedzony[N + 10];

long long int tryb;

int odwiedz_graf(long long int wierzcholek, long long int odwiedzony, long long int myto) {
	czy_odwiedzony[wierzcholek] = odwiedzony;
	
	if (tryb == 1) {
		max_wierzcholek = wierzcholek;
		max_zysk = miasta[wierzcholek] - myto;
	
	} else if (tryb > 1) {
		long long int zysk_w = miasta[wierzcholek] - myto;
		if (zysk_w > max_zysk) {
			max_zysk = zysk_w;
			max_wierzcholek = wierzcholek;
		
		} else if (zysk_w == max_zysk) {
			if (wierzcholek < max_wierzcholek) {	
				max_wierzcholek = wierzcholek;
			}
		}
	}
	
	for (list<krawedz>::iterator it = sasiedzi[wierzcholek].begin(); it != sasiedzi[wierzcholek].end(); ++it) {
		if (czy_odwiedzony[(*it).wierzcholek] != odwiedzony) {
			tryb++;
			odwiedz_graf((*it).wierzcholek, odwiedzony, myto + (*it).koszt);
		}
	}
	
	return max_wierzcholek;
}

int main() {
	long long int n, q, a, b, miasto;
	long long int koszt, zysk;
	krawedz k1, k2;
	long long int biezacy_wierzcholek = 1;
	
	scanf("%lld %lld", &n, &q);
	
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &miasta[i]);
	}
	
	for (int i = 0; i < n - 1; i++) {
		scanf("%lld %lld %lld", &a, &b, &koszt);
		
		k1 = {b, koszt};
		sasiedzi[a].push_back(k1);
		
		k2 = {a, koszt};
		sasiedzi[b].push_back(k2);
	}
	
	for (int i = 0; i < q; i++) {
		scanf("%lld", &tryb);
		
		if (tryb == 1) {
			scanf("%lld %lld", &miasto, &zysk);
			miasta[miasto] = zysk;
		
		} else if (tryb == 2) {
			scanf("%lld %lld %lld", &a, &b, &koszt);
			
			// zaktualizowa� koszt a -> b
			for (list<krawedz>::iterator it = sasiedzi[a].begin(); it != sasiedzi[a].end(); ++it) {
				if ((*it).wierzcholek == b) {
					(*it).koszt = koszt;
					break;
				}
			}
			
			// zaktualizowa� koszt b -> a
			for (list<krawedz>::iterator it = sasiedzi[b].begin(); it != sasiedzi[b].end(); ++it) {
				if ((*it).wierzcholek == a) {
					(*it).koszt = koszt;
				}
			}
		}
		
		tryb = 0L;
		biezacy_wierzcholek = odwiedz_graf(biezacy_wierzcholek, i + 1, 0);
		
		printf("%lld ", biezacy_wierzcholek);
	}
	
	return 0;
}