#include <iostream> #include <vector> #include <stack> using namespace std; typedef long long LL; const int MX = 100009; LL tab[MX]; int vis[MX]; vector< pair <int, LL > > graph[MX]; int n, q, last, ban; LL mx, cnt; int dfs(int flag, int s) { //cout << s << ' ' << cnt << ' ' << mx << ' ' << last << endl; if(s != ban && (cnt + tab[s] > mx || (cnt + tab[s] == mx && s < last))) { mx = cnt + tab[s]; last = s; } //cout << mx << ' ' << tab[s] << endl ; for(int i = 0; i < graph[s].size(); ++i) { if(vis[graph[s][i].first] != flag) { cnt -= graph[s][i].second; vis[graph[s][i].first] = flag; dfs(flag, graph[s][i].first); cnt += graph[s][i].second; } } } int main() { ios_base :: sync_with_stdio(0); int i, j, k, a, b; LL c; cin >> n >> q; for(i = 1; i <= n; ++i) vis[i] = 0; for(i = 1; i <= n; ++i) cin >> tab[i]; for(i = 0; i < n - 1; ++i) { cin >> a >> b >> c; graph[a].push_back(make_pair(b, c)); graph[b].push_back(make_pair(a, c)); } last = 1; int flag = 1; while(q--) { cin >> a; if(a == 1) { cin >> b >> c; tab[b] = c; } else { cin >> a >> b >> c; for(i = 0; i < graph[a].size(); ++i) if(graph[a][i].first == b) { graph[a][i].second = c; break; } for(i = 0; i < graph[b].size(); ++i) if(graph[b][i].first == a) { graph[b][i].second = c; break; } } mx = cnt = -1000000000000000000; cnt = 0; vis[last] = flag; ban = last; dfs(flag, last); ++flag; cout << last << ' '; // << "------\n"; } cout << '\n'; return 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 93 94 95 | #include <iostream> #include <vector> #include <stack> using namespace std; typedef long long LL; const int MX = 100009; LL tab[MX]; int vis[MX]; vector< pair <int, LL > > graph[MX]; int n, q, last, ban; LL mx, cnt; int dfs(int flag, int s) { //cout << s << ' ' << cnt << ' ' << mx << ' ' << last << endl; if(s != ban && (cnt + tab[s] > mx || (cnt + tab[s] == mx && s < last))) { mx = cnt + tab[s]; last = s; } //cout << mx << ' ' << tab[s] << endl ; for(int i = 0; i < graph[s].size(); ++i) { if(vis[graph[s][i].first] != flag) { cnt -= graph[s][i].second; vis[graph[s][i].first] = flag; dfs(flag, graph[s][i].first); cnt += graph[s][i].second; } } } int main() { ios_base :: sync_with_stdio(0); int i, j, k, a, b; LL c; cin >> n >> q; for(i = 1; i <= n; ++i) vis[i] = 0; for(i = 1; i <= n; ++i) cin >> tab[i]; for(i = 0; i < n - 1; ++i) { cin >> a >> b >> c; graph[a].push_back(make_pair(b, c)); graph[b].push_back(make_pair(a, c)); } last = 1; int flag = 1; while(q--) { cin >> a; if(a == 1) { cin >> b >> c; tab[b] = c; } else { cin >> a >> b >> c; for(i = 0; i < graph[a].size(); ++i) if(graph[a][i].first == b) { graph[a][i].second = c; break; } for(i = 0; i < graph[b].size(); ++i) if(graph[b][i].first == a) { graph[b][i].second = c; break; } } mx = cnt = -1000000000000000000; cnt = 0; vis[last] = flag; ban = last; dfs(flag, last); ++flag; cout << last << ' '; // << "------\n"; } cout << '\n'; return 0; } |