#include<cstdio> #include<vector> #include<utility> using namespace std; long long int tab[100001]; struct edge { int to; long long int val; }; vector<edge> tree[100001]; pair<int, long long int> dfs(int v, int p, long long int sum) { pair<int, long long int> res; res.first = v; res.second = (p == -1) ? -1000000000000000001LL : tab[v] - sum; for(const edge& e : tree[v]) { if(e.to != p) { auto dfsRes = dfs(e.to, v, sum + e.val); if(dfsRes.second > res.second || (dfsRes.second == res.second && dfsRes.first < res.first)) { res = dfsRes; } } } return res; } int main() { int n, q; scanf("%d %d", &n, &q); for(int i = 1; i <= n; i++) scanf("%lld", &tab[i]); for(int i = 1; i < n; i++) { int from, to; long long int val; scanf("%d %d %lld", &from, &to, &val); tree[from].push_back({to, val}); tree[to].push_back({from, val}); } int cur = 1; while(q) { int x; scanf("%d", &x); if(x == 1) { int v; long long int val; scanf("%d %lld", &v, &val); tab[v] = val; } else { int v1, v2; long long int val; scanf("%d %d %lld", &v1, &v2, &val); for(edge& e : tree[v1]) { if(e.to == v2) { e.val = val; break; } } for(edge& e : tree[v2]) { if(e.to == v1) { e.val = val; break; } } } auto curRes = dfs(cur, -1, 0); cur = curRes.first; printf("%d ", cur); --q; } printf("\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 | #include<cstdio> #include<vector> #include<utility> using namespace std; long long int tab[100001]; struct edge { int to; long long int val; }; vector<edge> tree[100001]; pair<int, long long int> dfs(int v, int p, long long int sum) { pair<int, long long int> res; res.first = v; res.second = (p == -1) ? -1000000000000000001LL : tab[v] - sum; for(const edge& e : tree[v]) { if(e.to != p) { auto dfsRes = dfs(e.to, v, sum + e.val); if(dfsRes.second > res.second || (dfsRes.second == res.second && dfsRes.first < res.first)) { res = dfsRes; } } } return res; } int main() { int n, q; scanf("%d %d", &n, &q); for(int i = 1; i <= n; i++) scanf("%lld", &tab[i]); for(int i = 1; i < n; i++) { int from, to; long long int val; scanf("%d %d %lld", &from, &to, &val); tree[from].push_back({to, val}); tree[to].push_back({from, val}); } int cur = 1; while(q) { int x; scanf("%d", &x); if(x == 1) { int v; long long int val; scanf("%d %lld", &v, &val); tab[v] = val; } else { int v1, v2; long long int val; scanf("%d %d %lld", &v1, &v2, &val); for(edge& e : tree[v1]) { if(e.to == v2) { e.val = val; break; } } for(edge& e : tree[v2]) { if(e.to == v1) { e.val = val; break; } } } auto curRes = dfs(cur, -1, 0); cur = curRes.first; printf("%d ", cur); --q; } printf("\n"); return 0; } |