#include <bits/stdc++.h> struct Droga{ int cel; long long cena; }; int target = -1; long long result = 0; void dfs(std::vector<Droga> tablica[], long long results[], long long ceny[], int current, int prev, long long koszty){ //std::cout << "CURRENT: " << current << "\n"; int next = -1; for (int i = 0; i < tablica[current].size(); i++){ next = tablica[current][i].cel; if (next != prev){ koszty += tablica[current][i].cena; results[next] = ceny[next] - koszty; if (results[next] >= result){ result = results[next]; target = next; } else if (results[next] == result){ if (next < target) target = next; } else if (target == -1){ result = results[next]; target = next; } dfs(tablica, results, ceny, next, current, koszty); } } return; } int main(){ std::ios_base::sync_with_stdio(0); std::cin.tie(NULL); int n, q; // liczba miast, dni std::cin >> n >> q; long long ceny[100005]; for (int i = 1; i <= n; i++) std::cin >> ceny[i]; // graf std::vector <Droga> tablica[100006]; int a, b; long long c; for (int i = 0; i < n-1; i++){ std::cin >> a >> b >> c; Droga d1; d1.cel = b; d1.cena = c; tablica[a].push_back(d1); d1.cel = a; tablica[b].push_back(d1); } // zmiany int rodzaj; int x; long long v; // do zmiany zysku, target, cena; // a, b, c uzywane do zmiany krawedzi int current = 1; long long results[100005]; long long koszty = 0; for (int i = 0; i < q; i++){ std::cin >> rodzaj; if (rodzaj == 1){ // zmiana zysku std::cin >> x >> v; ceny[x] = v; } else if (rodzaj == 2){ // zmiana krawedzi std::cin >> a >> b >> c; for (int i = 0; i < tablica[a].size(); i++) if (tablica[a][i].cel == b) tablica[a][i].cena = c; for (int i = 0; i < tablica[b].size(); i++) if (tablica[b][i].cel == a) tablica[b][i].cena = c; } //results = new long long[n]; koszty = 0; results[current] = 0; dfs(tablica, results, ceny, current, -1, koszty); std::cout << target << " "; current = target; target = -1; result = 0; } }
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 | #include <bits/stdc++.h> struct Droga{ int cel; long long cena; }; int target = -1; long long result = 0; void dfs(std::vector<Droga> tablica[], long long results[], long long ceny[], int current, int prev, long long koszty){ //std::cout << "CURRENT: " << current << "\n"; int next = -1; for (int i = 0; i < tablica[current].size(); i++){ next = tablica[current][i].cel; if (next != prev){ koszty += tablica[current][i].cena; results[next] = ceny[next] - koszty; if (results[next] >= result){ result = results[next]; target = next; } else if (results[next] == result){ if (next < target) target = next; } else if (target == -1){ result = results[next]; target = next; } dfs(tablica, results, ceny, next, current, koszty); } } return; } int main(){ std::ios_base::sync_with_stdio(0); std::cin.tie(NULL); int n, q; // liczba miast, dni std::cin >> n >> q; long long ceny[100005]; for (int i = 1; i <= n; i++) std::cin >> ceny[i]; // graf std::vector <Droga> tablica[100006]; int a, b; long long c; for (int i = 0; i < n-1; i++){ std::cin >> a >> b >> c; Droga d1; d1.cel = b; d1.cena = c; tablica[a].push_back(d1); d1.cel = a; tablica[b].push_back(d1); } // zmiany int rodzaj; int x; long long v; // do zmiany zysku, target, cena; // a, b, c uzywane do zmiany krawedzi int current = 1; long long results[100005]; long long koszty = 0; for (int i = 0; i < q; i++){ std::cin >> rodzaj; if (rodzaj == 1){ // zmiana zysku std::cin >> x >> v; ceny[x] = v; } else if (rodzaj == 2){ // zmiana krawedzi std::cin >> a >> b >> c; for (int i = 0; i < tablica[a].size(); i++) if (tablica[a][i].cel == b) tablica[a][i].cena = c; for (int i = 0; i < tablica[b].size(); i++) if (tablica[b][i].cel == a) tablica[b][i].cena = c; } //results = new long long[n]; koszty = 0; results[current] = 0; dfs(tablica, results, ceny, current, -1, koszty); std::cout << target << " "; current = target; target = -1; result = 0; } } |