#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <unordered_map> #include <map> #include <set> #include <stdio.h> using namespace std; typedef long long LL; const LL INF = 1e18 + 7; int n, q, p = 1; vector<int> g[100007]; map<pair<int, int>, LL> mp; LL w[100007]; bool odw[100007]; LL d[100007]; LL mx; void read() { cin >> n >> q; for(int i = 1; i <= n; i++) cin >> w[i]; for(int i = 1; i < n; i++) { int a, b; LL c; cin >> a >> b >> c; g[a].push_back(b); g[b].push_back(a); mp[{min(a, b), max(a, b)}] = c; } } void zer() { for(int i = 0; i <= n + 1; i++) odw[i] = 0, d[0] = 0ll; } void dfs(int s) { odw[s] = 1; for(int i = 0; i < (int)g[s].size(); i++) { int u = g[s][i]; if(!odw[u]) { d[u] = d[s] + mp[{min(u, s), max(u, s)}]; dfs(u); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); read(); for(int i = 1; i <= q; i++) { int x; cin >> x; if(x == 1) { int a; LL b; cin >> a >> b; w[a] = b; } if(x == 2) { int a, b, c; cin >> a >> b >> c; mp[{min(a, b), max(a, b)}] = c; } zer(); d[p] = 0; dfs(p); mx = -INF; int xx; for(int j = 1; j <= n; j++) { if(j == p) continue; //cout << w[j] << " " << d[j] << " " << j << endl; if(mx < w[j] - d[j]) { xx = j; mx = w[j] - d[j]; } } p = xx; cout << p << " "; } 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 96 97 98 99 100 | #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <unordered_map> #include <map> #include <set> #include <stdio.h> using namespace std; typedef long long LL; const LL INF = 1e18 + 7; int n, q, p = 1; vector<int> g[100007]; map<pair<int, int>, LL> mp; LL w[100007]; bool odw[100007]; LL d[100007]; LL mx; void read() { cin >> n >> q; for(int i = 1; i <= n; i++) cin >> w[i]; for(int i = 1; i < n; i++) { int a, b; LL c; cin >> a >> b >> c; g[a].push_back(b); g[b].push_back(a); mp[{min(a, b), max(a, b)}] = c; } } void zer() { for(int i = 0; i <= n + 1; i++) odw[i] = 0, d[0] = 0ll; } void dfs(int s) { odw[s] = 1; for(int i = 0; i < (int)g[s].size(); i++) { int u = g[s][i]; if(!odw[u]) { d[u] = d[s] + mp[{min(u, s), max(u, s)}]; dfs(u); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); read(); for(int i = 1; i <= q; i++) { int x; cin >> x; if(x == 1) { int a; LL b; cin >> a >> b; w[a] = b; } if(x == 2) { int a, b, c; cin >> a >> b >> c; mp[{min(a, b), max(a, b)}] = c; } zer(); d[p] = 0; dfs(p); mx = -INF; int xx; for(int j = 1; j <= n; j++) { if(j == p) continue; //cout << w[j] << " " << d[j] << " " << j << endl; if(mx < w[j] - d[j]) { xx = j; mx = w[j] - d[j]; } } p = xx; cout << p << " "; } return 0; } |