#include <bits/stdc++.h> using namespace std; inline void putUI(unsigned int n) { if(n==0) { putc_unlocked(48,stdout); return; } char tab[12]; int p = 0; while(n != 0) { tab[p++] = (n % 10) + 48; n /= 10; } while(p--) putc_unlocked(tab[p], stdout); } inline void readUI(int *n) { register char c = 0; while (c < 33) c = getc_unlocked(stdin); (*n) = 0; while (c > 32) {(*n) = (*n) * 10LL + (c - 48); c = getc_unlocked(stdin);} } inline void readULL(long long *n) { register char c = 0; while (c < 33) c = getc_unlocked(stdin); (*n) = 0; while (c > 32) {(*n) = (*n) * 10LL + (c - 48); c = getc_unlocked(stdin);} } const int maxn = 100111; int n, m, a, b; long long c, d[maxn], odl[maxn]; vector<pair<int, long long> > v[maxn]; void dfs(int u, int o) { for (auto i : v[u]) if (i.first != o) { odl[i.first] = odl[u] + i.second; dfs(i.first, u); } } int find(int x, int y) { int p = 0, k = v[x].size(); while (p < k) { int m = (p + k) / 2; if (v[x][m].first > y) k = m - 1; else p = m; if (p + 1 == k) { if (v[x][k].first == y) return k; else return p; } } return p; } int main () { readUI(&n); readUI(&m); //scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) readULL(&d[i]); for (int i = 1; i < n; i++) { readUI(&a);readUI(&b);readULL(&c); //scanf("%d%d%lld", &a, &b, &c); v[a].push_back({b, c}); v[b].push_back({a, c}); } for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end()); int akt = 1, akt2; long long res = 0LL; for (int i = 1; i <= m; i++) { scanf("%d", &a); if (a == 1) { scanf("%d%lld", &b, &c); d[b] = c; } else { scanf("%d%d%lld", &a, &b, &c); v[a][find(a, b)].second = c; v[b][find(b, a)].second = c; } dfs(akt, 0); res = -(1LL<<60); for (int j = 1; j <= n; j++) if (j != akt) { if (res < d[j] - odl[j]) { res = d[j] - odl[j]; akt2 = j; } } akt = akt2; putUI(akt); putc_unlocked(' ', stdout); //printf("%d ", akt); } putc_unlocked('\n', stdout); 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 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 | #include <bits/stdc++.h> using namespace std; inline void putUI(unsigned int n) { if(n==0) { putc_unlocked(48,stdout); return; } char tab[12]; int p = 0; while(n != 0) { tab[p++] = (n % 10) + 48; n /= 10; } while(p--) putc_unlocked(tab[p], stdout); } inline void readUI(int *n) { register char c = 0; while (c < 33) c = getc_unlocked(stdin); (*n) = 0; while (c > 32) {(*n) = (*n) * 10LL + (c - 48); c = getc_unlocked(stdin);} } inline void readULL(long long *n) { register char c = 0; while (c < 33) c = getc_unlocked(stdin); (*n) = 0; while (c > 32) {(*n) = (*n) * 10LL + (c - 48); c = getc_unlocked(stdin);} } const int maxn = 100111; int n, m, a, b; long long c, d[maxn], odl[maxn]; vector<pair<int, long long> > v[maxn]; void dfs(int u, int o) { for (auto i : v[u]) if (i.first != o) { odl[i.first] = odl[u] + i.second; dfs(i.first, u); } } int find(int x, int y) { int p = 0, k = v[x].size(); while (p < k) { int m = (p + k) / 2; if (v[x][m].first > y) k = m - 1; else p = m; if (p + 1 == k) { if (v[x][k].first == y) return k; else return p; } } return p; } int main () { readUI(&n); readUI(&m); //scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) readULL(&d[i]); for (int i = 1; i < n; i++) { readUI(&a);readUI(&b);readULL(&c); //scanf("%d%d%lld", &a, &b, &c); v[a].push_back({b, c}); v[b].push_back({a, c}); } for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end()); int akt = 1, akt2; long long res = 0LL; for (int i = 1; i <= m; i++) { scanf("%d", &a); if (a == 1) { scanf("%d%lld", &b, &c); d[b] = c; } else { scanf("%d%d%lld", &a, &b, &c); v[a][find(a, b)].second = c; v[b][find(b, a)].second = c; } dfs(akt, 0); res = -(1LL<<60); for (int j = 1; j <= n; j++) if (j != akt) { if (res < d[j] - odl[j]) { res = d[j] - odl[j]; akt2 = j; } } akt = akt2; putUI(akt); putc_unlocked(' ', stdout); //printf("%d ", akt); } putc_unlocked('\n', stdout); return 0; } |