#include <iostream> #include <vector> using namespace std; struct abc { long long x; long long w; }; long long wart[100005]; vector<abc> G[100005]; int kol=1; int odw[100005]; long long odl[100005]; void DFS(int v) { odw[v]=kol; for(int i=0; i<G[v].size(); i++) { long long s=G[v][i].x; long long w=G[v][i].w; if(odw[s]!=kol) { odl[s]=odl[v]+w; DFS(s); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int akt=1; long long n,q; cin>>n>>q; for(int i=1; i<=n; i++) { cin>>wart[i]; } for(int i=0; i<n-1; i++) { long long a,b,w; cin>>a>>b>>w; abc t; t.x=b; t.w=w; G[a].push_back(t); t.x=a; G[b].push_back(t); } for(int i=0; i<q; i++) { int k; cin>>k; if(k==1) { long long a,b; cin>>a>>b; wart[a]=b; } else { long long a,b,w; cin>>a>>b>>w; int j=0; while(G[a][j].x!=b)j++; G[a][j].w=w; j=0; while(G[b][j].x!=a)j++; G[b][j].w=w; } odl[akt]=0; DFS(akt); kol++; long long ma=-1000000000000000000; long long wierz=100000000; for(int i=1; i<=n; i++) { if(i!=akt) { if(wart[i]-odl[i]>ma) { ma=wart[i]-odl[i]; wierz=i; } } // cout<<" "<<i<<" "<<wart[i]<<" "<<odl[i]<<endl; } akt=wierz; cout<<akt<<" "; } //cin>>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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #include <iostream> #include <vector> using namespace std; struct abc { long long x; long long w; }; long long wart[100005]; vector<abc> G[100005]; int kol=1; int odw[100005]; long long odl[100005]; void DFS(int v) { odw[v]=kol; for(int i=0; i<G[v].size(); i++) { long long s=G[v][i].x; long long w=G[v][i].w; if(odw[s]!=kol) { odl[s]=odl[v]+w; DFS(s); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int akt=1; long long n,q; cin>>n>>q; for(int i=1; i<=n; i++) { cin>>wart[i]; } for(int i=0; i<n-1; i++) { long long a,b,w; cin>>a>>b>>w; abc t; t.x=b; t.w=w; G[a].push_back(t); t.x=a; G[b].push_back(t); } for(int i=0; i<q; i++) { int k; cin>>k; if(k==1) { long long a,b; cin>>a>>b; wart[a]=b; } else { long long a,b,w; cin>>a>>b>>w; int j=0; while(G[a][j].x!=b)j++; G[a][j].w=w; j=0; while(G[b][j].x!=a)j++; G[b][j].w=w; } odl[akt]=0; DFS(akt); kol++; long long ma=-1000000000000000000; long long wierz=100000000; for(int i=1; i<=n; i++) { if(i!=akt) { if(wart[i]-odl[i]>ma) { ma=wart[i]-odl[i]; wierz=i; } } // cout<<" "<<i<<" "<<wart[i]<<" "<<odl[i]<<endl; } akt=wierz; cout<<akt<<" "; } //cin>>n; } |