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 112 113 114 `#include #define FOR(x, b, e) for(int x = b; x <= (e); ++x) #define FORD(x, b,e) for(int x = b; x >= (e); --x) #define REP(x, b) for(int x = 0; x < (b); ++x) #define SIZE(c) ((int)c.size()) #define ALL(c) (c).begin(), (c).end() #define MP make_pair #define PB push_back #define ST first #define ND second using namespace std; typedef long long LL; typedef vector VI; typedef pair PII; typedef vector VPII; const int MAXN = 1e5 + 9; const LL INF2 = 1e9 + 33; const LL INF = INF2 * INF2; map mapa; VI tab[MAXN]; LL zysk[MAXN]; pair dfs(int poz, int p) { pair tmp, ans; ans.ND = poz; ans.ST = -INF; if(poz != p) ans = MP(zysk[poz], poz); REP(i, SIZE(tab[poz])) { if(tab[poz][i] != p) { tmp = dfs(tab[poz][i], poz); if(tmp.ST > ans.ST) ans = tmp; else if(tmp.ST == ans.ST) if(tmp.ND < ans.ND) ans = tmp; } } ans.ST -= mapa[MP(poz, p)]; return ans; } int main() { int n, q, a, b; LL c; cin>>n>>q; REP(i, n) scanf("%lld", &zysk[i]); REP(i, n - 1) { scanf("%d %d %lld", &a, &b, &c); a--; b--; tab[a].PB(b); tab[b].PB(a); mapa[MP(a, b)] = c; mapa[MP(b, a)] = c; } int poz = 0; REP(i, q) { scanf("%d", &a); if(a == 1) { scanf("%d %lld", &a, &c); a--; zysk[a] = c; } else { scanf("%d %d %lld", &a, &b, &c); a--; b--; mapa[MP(a, b)] = c; mapa[MP(b, a)] = c; } poz = dfs(poz, poz).ND; cout<