#include <bits/stdc++.h> using namespace std; int n, q; vector<pair<int, long long> > g[100005]; long long odl[100005]; long long wart[100005]; int dfs(int v, long long od, int oj) { odl[v]=od-wart[v]; for(int i=0; i<g[v].size(); i++) { if(g[v][i].first!=oj) { dfs(g[v][i].first, od+g[v][i].second, v); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i=1; i<=n; i++) { cin >> wart[i]; } for(int i=0; i<n-1; i++) { int a, b; long long c; cin >> a >> b >> c; g[a].push_back(make_pair(b,c)); g[b].push_back(make_pair(a,c)); } // cout << "\n"; int now = 1; for(int i=0; i<q; i++) { long long a; cin >> a; if(a==1) { long long b, c; cin >> b >> c; wart[b]=c; } if(a==2) { long long b, c, d; cin >> b >> c >> d; int rem, rem2; for(int j=0; j<g[b].size(); j++) { if(g[b][j].first == c) { rem = j; } } for(int j=0; j<g[c].size(); j++) { if(g[c][j].first == b) { rem2 = j; } } g[b][rem].second=d; g[c][rem2].second=d; } // cout << "asdfasdfasdf\n"; // for(int i=1; i<=n; i++) { // cout << i << ":\n"; // for(int j=0; j<g[i].size(); j++) { // cout << g[i][j].first << " " << g[i][j].second << "\n"; // } // } dfs(now, 0, 0); // for(int i=1; i<=n; i++) { // cout << i << " - " << odl[i] << "\n"; // } int id=-1; long long mini = 9223372036854775807; for(int j=1; j<=n; j++) { if(j!=now && odl[j]<mini) { mini=odl[j]; id=j; } } now = id; cout << id << " "; } }
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 | #include <bits/stdc++.h> using namespace std; int n, q; vector<pair<int, long long> > g[100005]; long long odl[100005]; long long wart[100005]; int dfs(int v, long long od, int oj) { odl[v]=od-wart[v]; for(int i=0; i<g[v].size(); i++) { if(g[v][i].first!=oj) { dfs(g[v][i].first, od+g[v][i].second, v); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i=1; i<=n; i++) { cin >> wart[i]; } for(int i=0; i<n-1; i++) { int a, b; long long c; cin >> a >> b >> c; g[a].push_back(make_pair(b,c)); g[b].push_back(make_pair(a,c)); } // cout << "\n"; int now = 1; for(int i=0; i<q; i++) { long long a; cin >> a; if(a==1) { long long b, c; cin >> b >> c; wart[b]=c; } if(a==2) { long long b, c, d; cin >> b >> c >> d; int rem, rem2; for(int j=0; j<g[b].size(); j++) { if(g[b][j].first == c) { rem = j; } } for(int j=0; j<g[c].size(); j++) { if(g[c][j].first == b) { rem2 = j; } } g[b][rem].second=d; g[c][rem2].second=d; } // cout << "asdfasdfasdf\n"; // for(int i=1; i<=n; i++) { // cout << i << ":\n"; // for(int j=0; j<g[i].size(); j++) { // cout << g[i][j].first << " " << g[i][j].second << "\n"; // } // } dfs(now, 0, 0); // for(int i=1; i<=n; i++) { // cout << i << " - " << odl[i] << "\n"; // } int id=-1; long long mini = 9223372036854775807; for(int j=1; j<=n; j++) { if(j!=now && odl[j]<mini) { mini=odl[j]; id=j; } } now = id; cout << id << " "; } } |