#include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; int main() { int n, q; cin >> n >> q; int i, j; vector <int> K; long long z[n]; for (i=0; i<n; i++) { cin >> z[i]; } vector <int> lista[n]; int a, b; long long c; for (i=0; i<n-1; i++) { cin >> a >> b >> c; lista[a-1].push_back(b-1); lista[a-1].push_back(c); lista[b-1].push_back(a-1); lista[b-1].push_back(c); } long long k[n]; int p[n]; int w; for (i=0; i<n; i++) { p[i]=0; k[i]=0; } int wynik2; int x=0; int l; long long wynik1=-1000000000000000000; int e, v, d, f, g, h; K.push_back(0); for (l=0; l<q; l++) { cin >> e; if (e==1) { cin >> v >> d; z[v-1]=d; } else { cin >> f >> g >> h; for (j=0; j<lista[f-1].size(); j++) { if (lista[f-1][j]==(g-1) && j%2==0) { lista[f-1][j+1]=h; } if (lista[g-1][j]==(f-1) && j%2==0) { lista[g-1][j+1]=h; } } } while (K.empty()==false) { w=K.back(); K.pop_back(); for (j=0; j<lista[w].size(); j++) { if (j%2==0) { if (p[lista[w][j]]==0) { k[lista[w][j]]=k[w]-lista[w][j+1]; p[lista[w][j]]=1; K.push_back(lista[w][j]); } } } } for (i=0; i<n; i++) { p[i]=0; k[i]+=z[i]; if (k[i]>wynik1 && i!=x) { wynik1=k[i]; wynik2=i; } k[i]=0; } cout << wynik2+1 << " "; wynik1=-1000000000000000000; K.push_back(wynik2); x=wynik2; } }
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 | #include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; int main() { int n, q; cin >> n >> q; int i, j; vector <int> K; long long z[n]; for (i=0; i<n; i++) { cin >> z[i]; } vector <int> lista[n]; int a, b; long long c; for (i=0; i<n-1; i++) { cin >> a >> b >> c; lista[a-1].push_back(b-1); lista[a-1].push_back(c); lista[b-1].push_back(a-1); lista[b-1].push_back(c); } long long k[n]; int p[n]; int w; for (i=0; i<n; i++) { p[i]=0; k[i]=0; } int wynik2; int x=0; int l; long long wynik1=-1000000000000000000; int e, v, d, f, g, h; K.push_back(0); for (l=0; l<q; l++) { cin >> e; if (e==1) { cin >> v >> d; z[v-1]=d; } else { cin >> f >> g >> h; for (j=0; j<lista[f-1].size(); j++) { if (lista[f-1][j]==(g-1) && j%2==0) { lista[f-1][j+1]=h; } if (lista[g-1][j]==(f-1) && j%2==0) { lista[g-1][j+1]=h; } } } while (K.empty()==false) { w=K.back(); K.pop_back(); for (j=0; j<lista[w].size(); j++) { if (j%2==0) { if (p[lista[w][j]]==0) { k[lista[w][j]]=k[w]-lista[w][j+1]; p[lista[w][j]]=1; K.push_back(lista[w][j]); } } } } for (i=0; i<n; i++) { p[i]=0; k[i]+=z[i]; if (k[i]>wynik1 && i!=x) { wynik1=k[i]; wynik2=i; } k[i]=0; } cout << wynik2+1 << " "; wynik1=-1000000000000000000; K.push_back(wynik2); x=wynik2; } } |