#include <cstdio> #include <vector> #include <bitset> #include <unordered_map> #include <queue> using namespace std; #define MX 100009 #define INF 1000000000000000009LL static int n, q; static vector<pair<int, long long>> edges[MX]; static unordered_map<int, int> indices[MX]; static bitset<MX> vis; static long long profit[MX]; static pair<int, long long> que[MX]; static int solve(int start){ int qpos = 0; que[qpos++] = {start, 0}; vis = 0; long long best = -INF; int bestfor = -1; vis[start] = 1; while(qpos){ auto cur = que[--qpos]; for(auto e: edges[cur.first]){ if(vis[e.first]) continue; vis[e.first] = 1; long long sumcost = cur.second + e.second; long long sumprofit = profit[e.first] - sumcost; if (sumprofit > best || (sumprofit == best && e.first < bestfor)) { best = sumprofit; bestfor = e.first; } que[qpos++] = {e.first, sumcost}; } } return bestfor; } int main(){ scanf("%d %d", &n, &q); for(int i=0; i<n; i++){ scanf("%lld", &profit[i]); } for(int i=1; i<n; i++){ int a, b; long long c; scanf("%d %d %lld", &a, &b, &c); a--; b--; indices[a][b] = edges[a].size(); edges[a].push_back({b, c}); indices[b][a] = edges[b].size(); edges[b].push_back({a, c}); } int cur = 0; while(q--){ int type; scanf("%d", &type); if(type == 1){ int v; long long d; scanf("%d %lld", &v, &d); v--; profit[v] = d; } else{ int a, b; long long d; scanf("%d %d %lld", &a, &b, &d); a--; b--; edges[a][indices[a][b]].second = d; edges[b][indices[b][a]].second = d; } cur = solve(cur); printf("%d ", cur + 1); } printf("\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 78 79 80 81 82 | #include <cstdio> #include <vector> #include <bitset> #include <unordered_map> #include <queue> using namespace std; #define MX 100009 #define INF 1000000000000000009LL static int n, q; static vector<pair<int, long long>> edges[MX]; static unordered_map<int, int> indices[MX]; static bitset<MX> vis; static long long profit[MX]; static pair<int, long long> que[MX]; static int solve(int start){ int qpos = 0; que[qpos++] = {start, 0}; vis = 0; long long best = -INF; int bestfor = -1; vis[start] = 1; while(qpos){ auto cur = que[--qpos]; for(auto e: edges[cur.first]){ if(vis[e.first]) continue; vis[e.first] = 1; long long sumcost = cur.second + e.second; long long sumprofit = profit[e.first] - sumcost; if (sumprofit > best || (sumprofit == best && e.first < bestfor)) { best = sumprofit; bestfor = e.first; } que[qpos++] = {e.first, sumcost}; } } return bestfor; } int main(){ scanf("%d %d", &n, &q); for(int i=0; i<n; i++){ scanf("%lld", &profit[i]); } for(int i=1; i<n; i++){ int a, b; long long c; scanf("%d %d %lld", &a, &b, &c); a--; b--; indices[a][b] = edges[a].size(); edges[a].push_back({b, c}); indices[b][a] = edges[b].size(); edges[b].push_back({a, c}); } int cur = 0; while(q--){ int type; scanf("%d", &type); if(type == 1){ int v; long long d; scanf("%d %lld", &v, &d); v--; profit[v] = d; } else{ int a, b; long long d; scanf("%d %d %lld", &a, &b, &d); a--; b--; edges[a][indices[a][b]].second = d; edges[b][indices[b][a]].second = d; } cur = solve(cur); printf("%d ", cur + 1); } printf("\n"); } |