#include <iostream> #include <map> #include <vector> using namespace std; long long n, q; map < pair<long long,long long>, long long > edges; long long v[100005]; vector <long long> lista[100005]; bool odw[100005]; pair<long long, long long> best; long long cost; int pre=1; void dfs( long long u ) { if( u != pre ) { if( v[u]-cost > best.second ) best = make_pair( u, v[u]-cost ); else if( v[u]-cost == best.second ) best.first = min( u, best.first ); } odw[u] = true; for(int i=0; i<lista[u].size(); i++) { if(!odw[ lista[u][i] ]) { cost += edges[ make_pair( min(u,lista[u][i]), max(u,lista[u][i]) ) ]; dfs(lista[u][i]); cost -= edges[ make_pair( min(u,lista[u][i]), max(u,lista[u][i]) ) ]; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>q; int a, b, d; for(int i=1; i<=n; i++) cin>>v[i]; for(int i=0; i<n-1; i++) { cin>>a>>b>>d; lista[a].push_back(b); lista[b].push_back(a); edges[ make_pair( min(a,b), max(a,b) ) ] = d; } int f; for(int i=0; i<q; i++) { cin>>f; if( f == 1 ) { cin>>a>>d; v[a] = d; } else { cin>>a>>b>>d; edges[ make_pair( min(a,b), max(a,b) ) ] = d; } best.second = -1e18; for(int i=0; i<=n; i++)odw[i] = false; dfs(pre); cout<<best.first<<" "; pre = best.first; } 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 | #include <iostream> #include <map> #include <vector> using namespace std; long long n, q; map < pair<long long,long long>, long long > edges; long long v[100005]; vector <long long> lista[100005]; bool odw[100005]; pair<long long, long long> best; long long cost; int pre=1; void dfs( long long u ) { if( u != pre ) { if( v[u]-cost > best.second ) best = make_pair( u, v[u]-cost ); else if( v[u]-cost == best.second ) best.first = min( u, best.first ); } odw[u] = true; for(int i=0; i<lista[u].size(); i++) { if(!odw[ lista[u][i] ]) { cost += edges[ make_pair( min(u,lista[u][i]), max(u,lista[u][i]) ) ]; dfs(lista[u][i]); cost -= edges[ make_pair( min(u,lista[u][i]), max(u,lista[u][i]) ) ]; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>q; int a, b, d; for(int i=1; i<=n; i++) cin>>v[i]; for(int i=0; i<n-1; i++) { cin>>a>>b>>d; lista[a].push_back(b); lista[b].push_back(a); edges[ make_pair( min(a,b), max(a,b) ) ] = d; } int f; for(int i=0; i<q; i++) { cin>>f; if( f == 1 ) { cin>>a>>d; v[a] = d; } else { cin>>a>>b>>d; edges[ make_pair( min(a,b), max(a,b) ) ] = d; } best.second = -1e18; for(int i=0; i<=n; i++)odw[i] = false; dfs(pre); cout<<best.first<<" "; pre = best.first; } return 0; } |