#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 100000 + 10; const LL INF = (LL)1e6 * (LL)1e6 * (LL)1e6 + 123; struct pair_hash { std::size_t operator () (const std::pair<int, int> &p) const { return (p.first << 16) + p.second; } }; int n,q; LL z[MAXN]; vector<int> G[MAXN]; unordered_map<pair<int, int>, LL, pair_hash> M; void set_edge(int a, int b, LL d) { if (a > b) swap(a, b); M[make_pair(a, b)] = d; } LL get_edge(int a, int b) { if (a > b) swap(a, b); return M[make_pair(a, b)]; } LL best; int bestv; int curr; LL dist; int vis[MAXN]; void dfs(int x) { vis[x] = 1; if ((z[x] - dist > best || (z[x] - dist == best && x < bestv)) && x != curr) { bestv = x; best = z[x] - dist; } for (auto y: G[x]) { if (!vis[y]) { auto e = get_edge(x, y); dist += e; dfs(y); dist -= e; } } } int main() { ios_base::sync_with_stdio(0); cin >> n >> q; for (int i = 0; i < n; i++) { cin >> z[i]; } for (int i = 0; i < n - 1; i++) { int a, b; LL c; cin >> a >> b >> c; a--; b--; G[a].push_back(b); G[b].push_back(a); set_edge(a, b, c); } curr = 0; for (int i = 0; i < q; i++) { int t; cin >> t; if (t == 1) { int v; LL d; cin >> v >> d; v--; z[v] = d; } else { int a, b; LL d; cin >> a >> b >> d; a--; b--; set_edge(a, b, d); } best = -INF; dist = 0; memset(vis, 0, sizeof(int) * n); dfs(curr); curr = bestv; cout << curr + 1 << " "; } 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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 100000 + 10; const LL INF = (LL)1e6 * (LL)1e6 * (LL)1e6 + 123; struct pair_hash { std::size_t operator () (const std::pair<int, int> &p) const { return (p.first << 16) + p.second; } }; int n,q; LL z[MAXN]; vector<int> G[MAXN]; unordered_map<pair<int, int>, LL, pair_hash> M; void set_edge(int a, int b, LL d) { if (a > b) swap(a, b); M[make_pair(a, b)] = d; } LL get_edge(int a, int b) { if (a > b) swap(a, b); return M[make_pair(a, b)]; } LL best; int bestv; int curr; LL dist; int vis[MAXN]; void dfs(int x) { vis[x] = 1; if ((z[x] - dist > best || (z[x] - dist == best && x < bestv)) && x != curr) { bestv = x; best = z[x] - dist; } for (auto y: G[x]) { if (!vis[y]) { auto e = get_edge(x, y); dist += e; dfs(y); dist -= e; } } } int main() { ios_base::sync_with_stdio(0); cin >> n >> q; for (int i = 0; i < n; i++) { cin >> z[i]; } for (int i = 0; i < n - 1; i++) { int a, b; LL c; cin >> a >> b >> c; a--; b--; G[a].push_back(b); G[b].push_back(a); set_edge(a, b, c); } curr = 0; for (int i = 0; i < q; i++) { int t; cin >> t; if (t == 1) { int v; LL d; cin >> v >> d; v--; z[v] = d; } else { int a, b; LL d; cin >> a >> b >> d; a--; b--; set_edge(a, b, d); } best = -INF; dist = 0; memset(vis, 0, sizeof(int) * n); dfs(curr); curr = bestv; cout << curr + 1 << " "; } cout << "\n"; return 0; } |