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
#include<iostream>
#include<vector>
using namespace std;
 
struct wierzcholki{
  vector <unsigned int> polaczenia;
  vector <unsigned int> koszt;  
  bool odwiedzony; 
  int cena;
  int wynik;
}*w;
 
int w_glab(int k, int suma)
{
  w[k].odwiedzony = 1;
  for(int i=0; i<w[k].polaczenia.size(); i++)
    if(!w[w[k].polaczenia[i]].odwiedzony) {
    	suma-=w[k].koszt[i];
    	if(w[0].wynik<=w[w[k].polaczenia[i]].cena+suma){
    		if (w[0].wynik==w[w[k].polaczenia[i]].cena+suma){
    			if (w[1].wynik>w[k].polaczenia[i]){
    				w[0].wynik=w[w[k].polaczenia[i]].cena+suma;
					w[1].wynik=w[k].polaczenia[i];
				}
			}
			else{
				w[0].wynik=w[w[k].polaczenia[i]].cena+suma;
				w[1].wynik=w[k].polaczenia[i];
			}	
		}
    	w_glab(w[k].polaczenia[i],suma); 
    	suma+=w[k].koszt[i];
  	}
}
 
int main()
{
  unsigned int n, pol, pocz, a, b, koszt,days;
  cin>>n;
  pol=n-1;
  pocz=1;
  cin>>days;
  w = new wierzcholki[n+1];
  for (int i=1;i<=n;i++){
  	int x;
  	cin>>x;
  	w[i].cena=x;
  }
  for(int i=0; i<pol; i++){
    cin>>a>>b>>koszt;
    w[a].polaczenia.push_back(b);
    w[a].koszt.push_back(koszt);
    w[b].polaczenia.push_back(a);
    w[b].koszt.push_back(koszt);
	}
  for (int j=0;j<days;j++){
  	int z,d;
  	cin>>z;
  	if (z==1){
  		cin>>a>>d;
  		w[a].cena=d;
  	}
  	else {
  		cin>>a>>b>>d;
  		for(int i=0; i<w[a].polaczenia.size(); i++){
  			if (w[a].polaczenia[i]==b){
  				w[a].koszt[i]=d;
  				break;
		  	}
		}
		for(int i=0; i<w[b].polaczenia.size(); i++){
  			if (w[b].polaczenia[i]==a){
  				w[b].koszt[i]=d;
  				break;
		  	}
	  	}	
  	}
  	w[0].wynik=w[w[pocz].polaczenia[0]].cena-w[pocz].koszt[0];
  	w[1].wynik=w[pocz].polaczenia[0];
  	w_glab(pocz,0);
  	cout<<w[1].wynik<<" ";
  	for(int i=1;i<=n;i++){
  		w[i].odwiedzony = 0;
  	}
  	pocz=w[1].wynik;
}
  
  return 0;
}