#define dbg if(0) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const int MAX_SIZE = 100010; ll z[MAX_SIZE]; ll c[MAX_SIZE]; ll val[MAX_SIZE]; vector<pll> V[MAX_SIZE]; void clean(int n){ for(int i = 0; i <= n; ++i){ c[i] = 0; val[i] = 0; } } void dfs(int current){ c[current] = 1; for(pll& x : V[current]){ dbg cout << "current: " << current << " x.first: " << x.first << " c: " << c[x.first] << endl; if(c[x.first] == 0){ val[x.first] = val[current] + x.second; dfs(x.first); } } } int main(){ int n, q; cin >> n >> q; for(int i = 1; i <= n; ++i){ cin >> z[i]; } ll a, b, c; for(int i = 0; i < n-1; ++i){ cin >> a >> b >> c; V[a].push_back(pll(b,c)); V[b].push_back(pll(a,c)); } ll current = 1; ll command, v, d; for(int i = 0; i < q; ++i){ cin >> command; if(command==1){ cin >> v >> d; z[v] = d; } if(command==2){ cin >> a >> b >> d; for(pll& x : V[a]){ if(x.first == b){ x.second = d; break; } } for(pll& x : V[b]){ if(x.first == a){ x.second = d; break; } } } dbg cout << "command: " << command << " current: " << current << endl; clean(n); dfs(current); pll best(0, numeric_limits<ll>::min()); for(int i = 1; i <= n; ++i){ dbg cout << "i: " << i << " val: " << val[i] << " z: " << z[i] << endl; if(i != current && -val[i] + z[i] > best.second){ best.first = i; best.second = -val[i] + z[i]; } } current = best.first; cout << best.first << " "; } 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 | #define dbg if(0) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const int MAX_SIZE = 100010; ll z[MAX_SIZE]; ll c[MAX_SIZE]; ll val[MAX_SIZE]; vector<pll> V[MAX_SIZE]; void clean(int n){ for(int i = 0; i <= n; ++i){ c[i] = 0; val[i] = 0; } } void dfs(int current){ c[current] = 1; for(pll& x : V[current]){ dbg cout << "current: " << current << " x.first: " << x.first << " c: " << c[x.first] << endl; if(c[x.first] == 0){ val[x.first] = val[current] + x.second; dfs(x.first); } } } int main(){ int n, q; cin >> n >> q; for(int i = 1; i <= n; ++i){ cin >> z[i]; } ll a, b, c; for(int i = 0; i < n-1; ++i){ cin >> a >> b >> c; V[a].push_back(pll(b,c)); V[b].push_back(pll(a,c)); } ll current = 1; ll command, v, d; for(int i = 0; i < q; ++i){ cin >> command; if(command==1){ cin >> v >> d; z[v] = d; } if(command==2){ cin >> a >> b >> d; for(pll& x : V[a]){ if(x.first == b){ x.second = d; break; } } for(pll& x : V[b]){ if(x.first == a){ x.second = d; break; } } } dbg cout << "command: " << command << " current: " << current << endl; clean(n); dfs(current); pll best(0, numeric_limits<ll>::min()); for(int i = 1; i <= n; ++i){ dbg cout << "i: " << i << " val: " << val[i] << " z: " << z[i] << endl; if(i != current && -val[i] + z[i] > best.second){ best.first = i; best.second = -val[i] + z[i]; } } current = best.first; cout << best.first << " "; } return 0; } |