#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define st first #define nd second #define inf 1000000000000000009 using namespace std; long long z[100000]; vector<pair<int, long long> > g[100000]; long long value[100000]; void DFS(int v, int u, long long cost){ for(int i=0; i<g[v].size(); i++){ if(g[v][i].st!=u){ value[g[v][i].st]=z[g[v][i].st]-(cost+g[v][i].nd); DFS(g[v][i].st, v, cost+g[v][i].nd); } } } int main(){ ios_base::sync_with_stdio(0); int n, q, a, b, dec, last=0; long long c; cin>>n>>q; for(int i=0; i<n; i++){ cin>>z[i]; } for(int i=0; i<n-1; i++){ cin>>a>>b>>c; a--; b--; g[a].pb(mp(b, c)); g[b].pb(mp(a, c)); } for(int i=0; i<q; i++){ cin>>dec; if(dec==1){ cin>>a>>c; a--; z[a]=c; } else{ cin>>a>>b>>c; a--; b--; for(int j=0; j<g[a].size(); j++){ if(g[a][j].st==b){ g[a][j].nd=c; break; } } for(int j=0; j<g[b].size(); j++){ if(g[b][j].st==a){ g[b][j].nd=c; break; } } } DFS(last, last, 0); long long mx=-inf; value[last]=-inf; for(int i=0; i<n; i++){ if(value[i]>mx){ mx=value[i]; last=i; } } cout<<last+1<<' '; } 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 <bits/stdc++.h> #define pb push_back #define mp make_pair #define st first #define nd second #define inf 1000000000000000009 using namespace std; long long z[100000]; vector<pair<int, long long> > g[100000]; long long value[100000]; void DFS(int v, int u, long long cost){ for(int i=0; i<g[v].size(); i++){ if(g[v][i].st!=u){ value[g[v][i].st]=z[g[v][i].st]-(cost+g[v][i].nd); DFS(g[v][i].st, v, cost+g[v][i].nd); } } } int main(){ ios_base::sync_with_stdio(0); int n, q, a, b, dec, last=0; long long c; cin>>n>>q; for(int i=0; i<n; i++){ cin>>z[i]; } for(int i=0; i<n-1; i++){ cin>>a>>b>>c; a--; b--; g[a].pb(mp(b, c)); g[b].pb(mp(a, c)); } for(int i=0; i<q; i++){ cin>>dec; if(dec==1){ cin>>a>>c; a--; z[a]=c; } else{ cin>>a>>b>>c; a--; b--; for(int j=0; j<g[a].size(); j++){ if(g[a][j].st==b){ g[a][j].nd=c; break; } } for(int j=0; j<g[b].size(); j++){ if(g[b][j].st==a){ g[b][j].nd=c; break; } } } DFS(last, last, 0); long long mx=-inf; value[last]=-inf; for(int i=0; i<n; i++){ if(value[i]>mx){ mx=value[i]; last=i; } } cout<<last+1<<' '; } return 0; } |