#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define MP make_pair #define PB push_back #define ST first #define ND second ll *val; int *p; vector<pll> *v; map<pll, int> mapa; pll dfs(int a, int p) { pll res; res.ST = a; res.ND = val[a]; for(int i=0; i < v[a].size(); i++) { int b = v[a][i].ST; if(b!=p) { pll x = dfs(b, a); x.ND-=v[a][i].ND; if(x.ND > res.ND || (x.ND == res.ND && x.ST < res.ST)) { res = x; } } } return res; } int main() { ios_base::sync_with_stdio(0); int n, q; cin >> n >> q; v = new vector<pll> [n+1]; val = new ll[n+1]; p = new int[n]; for(int i=1; i<= n; i++) { cin >> val[i]; } for(int i=1; i < n; i++) { ll a, b, c; cin >> a >> b >> c; v[a].PB(MP(b, c)); v[b].PB(MP(a, c)); mapa.insert(MP(MP(a, b), v[a].size()-1)); mapa.insert(MP(MP(b, a), v[b].size()-1)); } int sta=1; for(int i=0; i < q; i++) { int type; cin >> type; if(type==1) { ll a, b; cin >> a >> b; val[a] = b; } else { int a, b; ll c; cin >> a >> b >> c; auto it = mapa.find(MP(a, b)); v[a][it->second].ND = c; it = mapa.find(MP(b, a)); v[b][it->second].ND = c; } ll pom = val[sta]; val[sta] = -1e18; pll x = dfs(sta, -1); val[sta] = pom; sta = x.ST; cout << sta << " "; } 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 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define MP make_pair #define PB push_back #define ST first #define ND second ll *val; int *p; vector<pll> *v; map<pll, int> mapa; pll dfs(int a, int p) { pll res; res.ST = a; res.ND = val[a]; for(int i=0; i < v[a].size(); i++) { int b = v[a][i].ST; if(b!=p) { pll x = dfs(b, a); x.ND-=v[a][i].ND; if(x.ND > res.ND || (x.ND == res.ND && x.ST < res.ST)) { res = x; } } } return res; } int main() { ios_base::sync_with_stdio(0); int n, q; cin >> n >> q; v = new vector<pll> [n+1]; val = new ll[n+1]; p = new int[n]; for(int i=1; i<= n; i++) { cin >> val[i]; } for(int i=1; i < n; i++) { ll a, b, c; cin >> a >> b >> c; v[a].PB(MP(b, c)); v[b].PB(MP(a, c)); mapa.insert(MP(MP(a, b), v[a].size()-1)); mapa.insert(MP(MP(b, a), v[b].size()-1)); } int sta=1; for(int i=0; i < q; i++) { int type; cin >> type; if(type==1) { ll a, b; cin >> a >> b; val[a] = b; } else { int a, b; ll c; cin >> a >> b >> c; auto it = mapa.find(MP(a, b)); v[a][it->second].ND = c; it = mapa.find(MP(b, a)); v[b][it->second].ND = c; } ll pom = val[sta]; val[sta] = -1e18; pll x = dfs(sta, -1); val[sta] = pom; sta = x.ST; cout << sta << " "; } return 0; } |