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
#include<iostream>
#include<vector>
using namespace std;

long long zarobek_max=0;
int id_max;

struct wierzcholki{
  vector < pair < long long, long long > > polaczenia; //połączenia wychodzące z danego wierzchołka
  bool odwiedzony; //okresla, czy wierzchołek został odwiedzony
  long long zarobek;//dodatkowe dane dla danego wierzchołka
  //........................
  //........................
}*w;

void w_glab(int k, long long koszt, long long dojazd, int pocz)
{
  w[k].odwiedzony = 1;
  
	  koszt+=dojazd;
	  
	if(w[k].zarobek-koszt>zarobek_max||id_max==pocz){
	  	zarobek_max = w[k].zarobek-koszt;
	  	id_max=k;
	  }else if(w[k].zarobek-koszt==zarobek_max&&k<id_max){
	  		zarobek_max = w[k].zarobek-koszt;
	  		id_max=k;
	}
  for(int i=0; i<w[k].polaczenia.size(); i++){
  //jesli wierzchołek, do którego chcemy przejsć nie został
  //jeszcze odwiedzony
    if(!w[w[k].polaczenia[i].first].odwiedzony) 
    //to przechodzimy do niego
      w_glab(w[k].polaczenia[i].first, koszt, w[k].polaczenia[i].second, pocz);
	}
}

int main(){
	int n, q, pocz=0, a, b;
	long long zarobek, koszt=0, dojazd=0;
	id_max=pocz;
	
	scanf("%d%d", &n, &q);
	
	 w = new wierzcholki[n+1];
	 
	for(int i=0; i<n; i++){
		scanf("%lld", &zarobek);
		w[i].zarobek = zarobek;
	}
	
	for(int i=0; i<n-1; i++){
		scanf("%d%d%lld", &a, &b, &koszt);
		w[a-1].polaczenia.push_back(make_pair(b-1, koszt));
		w[b-1].polaczenia.push_back(make_pair(a-1, koszt));
	}
	
	for(int i = 0; i < q; i++){
		
		int zmiana;
		scanf("%d", &zmiana);
		
		if(zmiana==1){
			int zmiana_id;
			scanf("%d", &zmiana_id);
			zmiana_id--;
			scanf("%lld", &w[zmiana_id].zarobek);
		}else{
			int zmiana_id_1;
			int zmiana_id_2;
			long long zmiana_koszt;
			scanf("%d%d%lld", &zmiana_id_1, &zmiana_id_2, &zmiana_koszt);
			zmiana_id_1--;
			zmiana_id_2--;
			
			for(int j=0; j<w[zmiana_id_1].polaczenia.size(); j++){
				if(w[zmiana_id_1].polaczenia[j].first==zmiana_id_2){
					w[zmiana_id_1].polaczenia[j].second = zmiana_koszt;
				}
			}
			
			for(int j=0; j<w[zmiana_id_2].polaczenia.size(); j++){
				if(w[zmiana_id_2].polaczenia[j].first==zmiana_id_1){
					w[zmiana_id_2].polaczenia[j].second = zmiana_koszt;
				}
			}
		}
		
		zarobek=w[id_max].zarobek;
		w_glab(id_max, koszt, dojazd, pocz);
		pocz = id_max;
		if(i+1!=q){
			for(int j =0; j < n; j++){
				w[j].odwiedzony=0;
			}
		}
		printf("%d ", id_max+1);
	}
}