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 #include #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define all(v) (v).begin(),(v).end() #define PII pair #define mp make_pair #define st first #define nd second #define pb push_back #define lint long long int #define VI vector #define debug(x) {cerr <<#x <<" = " < strata[max_n]; int xi, yi; lint ci; lint huhu[max_n]; void dfs(int v, int p) { FOR(i,0,g[v].size()) { int w = g[v][i]; if (v == xi && w == yi) strata[v][i] = ci; if (w == p) continue; huhu[w] = huhu[v] + strata[v][i]; dfs(w, v); } } int licz(int x) { FOR(i,0,n) huhu[i] = 0; dfs(x,-1); int kto = (x == 0) ? 1 : 0; FOR(i,0,n) { if (i!=x && zisk[i]-huhu[i] > zisk[kto]-huhu[kto]) { kto = i; } } return kto; } int main() { read2(n, q); FOR(i,0,n) { lint a; scanf("%lld", &a); zisk[i] = a; } FOR(i,0,n-1) { int a, b; lint c; scanf("%d%d%lld",&a,&b,&c); a--; b--; g[a].pb(b); g[b].pb(a); strata[a].pb(c); strata[b].pb(c); } int gdzie = 0; while (q--) { make(type); if (type == 1) { make(v); v--; lint d; scanf("%lld", &d); zisk[v] = d; } else { int a, b; lint c; scanf("%d%d%lld",&a, &b, &c); a--; b--; xi = a, yi = b, ci = c; } gdzie = licz(gdzie); printf("%d ", gdzie + 1); } printf("\n"); }