#include<bits/stdc++.h> #define MAX 100001 using namespace std; long long tab[MAX]; int odwiedzone[MAX]; vector< pair <int, long long > > graf[MAX]; int n, q, ostatni, niedostepny; long long maksymalny, porownywalny; void init(); bool dfsCondition(int kolejka); void updatePath(int a); int dfs(int indeks, int kolejka) { if(dfsCondition(kolejka)) { maksymalny = porownywalny + tab[kolejka]; ostatni = kolejka; } for(int i = 0; i < graf[kolejka].size(); ++i) { if(odwiedzone[graf[kolejka][i].first] != indeks) { porownywalny -= graf[kolejka][i].second; odwiedzone[graf[kolejka][i].first] = indeks; dfs(indeks, graf[kolejka][i].first); porownywalny += graf[kolejka][i].second; } } } int main() { int k, a; cin >> n >> q; init(); ostatni = 1; int indeks = 1; while(q--) { cin >> a; updatePath(a); maksymalny = -1000; porownywalny = 0; odwiedzone[ostatni] = indeks; niedostepny = ostatni; dfs(indeks, ostatni); indeks++; cout << ostatni << ' '; } puts(""); } void init() { long long a, b, c; for(int i = 1; i <= n; i++) odwiedzone[i] = 0; for(int i = 1; i <= n; i++) cin >> tab[i]; for(int i = 0; i < n-1; i++) { cin >> a >> b >> c; graf[a].push_back(make_pair(b, c)); graf[b].push_back(make_pair(a, c)); } } bool dfsCondition(int kolejka) { return kolejka != niedostepny && (porownywalny + tab[kolejka] > maksymalny || (porownywalny + tab[kolejka] == maksymalny && kolejka < ostatni)); } void updatePath(int a) { long long b, c; if(a == 1) { cin >> b >> c; tab[b] = c; } else { cin >> a >> b >> c; for(int i = 0; i < graf[a].size(); ++i) if(graf[a][i].first == b) { graf[a][i].second = c; break; } for(int i = 0; i < graf[b].size(); ++i) if(graf[b][i].first == a) { graf[b][i].second = c; break; } } }
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> #define MAX 100001 using namespace std; long long tab[MAX]; int odwiedzone[MAX]; vector< pair <int, long long > > graf[MAX]; int n, q, ostatni, niedostepny; long long maksymalny, porownywalny; void init(); bool dfsCondition(int kolejka); void updatePath(int a); int dfs(int indeks, int kolejka) { if(dfsCondition(kolejka)) { maksymalny = porownywalny + tab[kolejka]; ostatni = kolejka; } for(int i = 0; i < graf[kolejka].size(); ++i) { if(odwiedzone[graf[kolejka][i].first] != indeks) { porownywalny -= graf[kolejka][i].second; odwiedzone[graf[kolejka][i].first] = indeks; dfs(indeks, graf[kolejka][i].first); porownywalny += graf[kolejka][i].second; } } } int main() { int k, a; cin >> n >> q; init(); ostatni = 1; int indeks = 1; while(q--) { cin >> a; updatePath(a); maksymalny = -1000; porownywalny = 0; odwiedzone[ostatni] = indeks; niedostepny = ostatni; dfs(indeks, ostatni); indeks++; cout << ostatni << ' '; } puts(""); } void init() { long long a, b, c; for(int i = 1; i <= n; i++) odwiedzone[i] = 0; for(int i = 1; i <= n; i++) cin >> tab[i]; for(int i = 0; i < n-1; i++) { cin >> a >> b >> c; graf[a].push_back(make_pair(b, c)); graf[b].push_back(make_pair(a, c)); } } bool dfsCondition(int kolejka) { return kolejka != niedostepny && (porownywalny + tab[kolejka] > maksymalny || (porownywalny + tab[kolejka] == maksymalny && kolejka < ostatni)); } void updatePath(int a) { long long b, c; if(a == 1) { cin >> b >> c; tab[b] = c; } else { cin >> a >> b >> c; for(int i = 0; i < graf[a].size(); ++i) if(graf[a][i].first == b) { graf[a][i].second = c; break; } for(int i = 0; i < graf[b].size(); ++i) if(graf[b][i].first == a) { graf[b][i].second = c; break; } } } |