#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 1e5+5; const ll INF = 1e18; map<pair<int, int>, ll> E; ll dist[MAXN], z[MAXN]; vector<int> G[MAXN]; int n; void calcDists(int v, int p) { for (int u : G[v]) { if (u == p) continue; dist[u] = dist[v] + E[{v, u}]; calcDists(u, v); } } int ansQuery(int v) { calcDists(v, -1); ll maks = -INF; int which = 0; for (int i = 1; i <= n; i++) { if (z[i] - dist[i] > maks && i != v) { maks = z[i] - dist[i]; which = i; } } return which; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> z[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); E[{a, b}] = E[{b, a}] = c; } int cur = 1; for (int i = 0; i < q; i++) { int x; cin >> x; if (x == 1) { int v; ll d; cin >> v >> d; z[v] = d; } else { int a, b; ll c; cin >> a >> b >> c; E[{a, b}] = E[{b, a}] = c; } cur = ansQuery(cur); cout << cur << " "; } cout << "\n"; }
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 | #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 1e5+5; const ll INF = 1e18; map<pair<int, int>, ll> E; ll dist[MAXN], z[MAXN]; vector<int> G[MAXN]; int n; void calcDists(int v, int p) { for (int u : G[v]) { if (u == p) continue; dist[u] = dist[v] + E[{v, u}]; calcDists(u, v); } } int ansQuery(int v) { calcDists(v, -1); ll maks = -INF; int which = 0; for (int i = 1; i <= n; i++) { if (z[i] - dist[i] > maks && i != v) { maks = z[i] - dist[i]; which = i; } } return which; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> z[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); E[{a, b}] = E[{b, a}] = c; } int cur = 1; for (int i = 0; i < q; i++) { int x; cin >> x; if (x == 1) { int v; ll d; cin >> v >> d; z[v] = d; } else { int a, b; ll c; cin >> a >> b >> c; E[{a, b}] = E[{b, a}] = c; } cur = ansQuery(cur); cout << cur << " "; } cout << "\n"; } |