#include <bits/stdc++.h> using namespace std; #define ff first #define dd second #define mp make_pair #define pb push_back #define sz size() #define For(i,s,a) for(int i=s;i<a;++i) #define reg register #define ci const int & #define fff ff.ff #define ffd ff.dd #define ddf dd.ff #define ddd dd.dd #define pii pair<int,int> #define pll pair<lld,lld> #define piii pair<pii,int> #define N (int)(1000001) #define lld long long #define mod (lld)(1e9+7) #define getchar_unlocked getchar inline void scan(lld *i); lld m[100001]; map<int,lld> pol[2001]; vector<int>c[100001]; int tmp; lld maxn; bitset<100001>odw; void dfs(int x, int k) { // cout<<x<<" xd "<<k<<" "<<m[x]<<endl; odw[x]=1; if(m[x]-k>maxn) { tmp=x; maxn=m[x]-k; } else if(m[x]-k==maxn) tmp=min(tmp,x); For(i,0,c[x].sz) if(!odw[c[x][i]]) dfs(c[x][i],k+pol[x][c[x][i]]); } int main() { lld k; int a,t,g,h,x; scanf("%d%d", &a,&t); For(i,0,a) scanf("%lld", &m[i+1]); For(i,0,a-1) { scanf("%d%d%lld",&g,&h,&k); pol[g][h]=pol[h][g]=k; c[g].pb(h); c[h].pb(g); } x=1; while(t--) { scanf("%d", &g); if(g&1) { scanf("%d%lld",&g,&k); m[g]=k; } else { scanf("%d%d%lld", &g,&h,&k); pol[g][h]=pol[h][g]=k; } odw=0; tmp=0; maxn=0; odw[x]=1; For(i,0,c[x].sz) dfs(c[x][i],pol[x][c[x][i]]); x=tmp; printf("%d ",x); } } inline void scan(lld* i) { lld t=0; char c; bool neg=false; c=getchar_unlocked(); while(c<'0'||c>'9') { if(c=='-') neg=true; c=getchar_unlocked(); } while(c>='0'&&c<='9') { t=(t<<3)+(t<<1)+c-'0'; c=getchar_unlocked(); } if(neg) t=~(t-1); //neg *i=t; }
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 | #include <bits/stdc++.h> using namespace std; #define ff first #define dd second #define mp make_pair #define pb push_back #define sz size() #define For(i,s,a) for(int i=s;i<a;++i) #define reg register #define ci const int & #define fff ff.ff #define ffd ff.dd #define ddf dd.ff #define ddd dd.dd #define pii pair<int,int> #define pll pair<lld,lld> #define piii pair<pii,int> #define N (int)(1000001) #define lld long long #define mod (lld)(1e9+7) #define getchar_unlocked getchar inline void scan(lld *i); lld m[100001]; map<int,lld> pol[2001]; vector<int>c[100001]; int tmp; lld maxn; bitset<100001>odw; void dfs(int x, int k) { // cout<<x<<" xd "<<k<<" "<<m[x]<<endl; odw[x]=1; if(m[x]-k>maxn) { tmp=x; maxn=m[x]-k; } else if(m[x]-k==maxn) tmp=min(tmp,x); For(i,0,c[x].sz) if(!odw[c[x][i]]) dfs(c[x][i],k+pol[x][c[x][i]]); } int main() { lld k; int a,t,g,h,x; scanf("%d%d", &a,&t); For(i,0,a) scanf("%lld", &m[i+1]); For(i,0,a-1) { scanf("%d%d%lld",&g,&h,&k); pol[g][h]=pol[h][g]=k; c[g].pb(h); c[h].pb(g); } x=1; while(t--) { scanf("%d", &g); if(g&1) { scanf("%d%lld",&g,&k); m[g]=k; } else { scanf("%d%d%lld", &g,&h,&k); pol[g][h]=pol[h][g]=k; } odw=0; tmp=0; maxn=0; odw[x]=1; For(i,0,c[x].sz) dfs(c[x][i],pol[x][c[x][i]]); x=tmp; printf("%d ",x); } } inline void scan(lld* i) { lld t=0; char c; bool neg=false; c=getchar_unlocked(); while(c<'0'||c>'9') { if(c=='-') neg=true; c=getchar_unlocked(); } while(c>='0'&&c<='9') { t=(t<<3)+(t<<1)+c-'0'; c=getchar_unlocked(); } if(neg) t=~(t-1); //neg *i=t; } |