fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 100005;
  5. struct Node {
  6.     long long sum, pref, suff, ans;
  7.     bool is_null;
  8.  
  9.     Node() {
  10.         is_null = true;
  11.         sum = pref = suff = ans = 0;
  12.     }
  13.  
  14.     Node(long long val) {
  15.         is_null = false;
  16.         sum = val;
  17.         pref = suff = ans = max(0LL, val);
  18.     }
  19. };
  20.  
  21. Node merge(const Node& L, const Node& R) {
  22.     if (L.is_null) return R;
  23.     if (R.is_null) return L;
  24.     Node res;
  25.     res.is_null = false;
  26.     res.sum = L.sum + R.sum;
  27.     res.pref = max(L.pref, L.sum + R.pref);
  28.     res.suff = max(R.suff, R.sum + L.suff);
  29.     res.ans = max({L.ans, R.ans, L.suff + R.pref});
  30.     return res;
  31. }
  32.  
  33. Node reverse_node(Node A) {
  34.     if (A.is_null) return A;
  35.     swap(A.pref, A.suff);
  36.     return A;
  37. }
  38.  
  39. int n, q;
  40. int A[MAXN];
  41. vector<int> adj[MAXN];
  42.  
  43. int parent_node[MAXN], depth[MAXN], heavy[MAXN], head[MAXN], pos[MAXN], sz[MAXN];
  44. int cur_pos = 0;
  45. int arr[MAXN]; 
  46.  
  47. void dfs_sz(int v, int p, int d) {
  48.     sz[v] = 1;
  49.     parent_node[v] = p;
  50.     depth[v] = d;
  51.     heavy[v] = -1;
  52.     int max_sub = 0;
  53.     for (int u : adj[v]) {
  54.         if (u != p) {
  55.             dfs_sz(u, v, d + 1);
  56.             sz[v] += sz[u];
  57.             if (sz[u] > max_sub) {
  58.                 max_sub = sz[u];
  59.                 heavy[v] = u;
  60.             }
  61.         }
  62.     }
  63. }
  64.  
  65. void dfs_hld(int v, int p, int h) {
  66.     head[v] = h;
  67.     pos[v] = ++cur_pos;
  68.     arr[cur_pos] = A[v];
  69.  
  70.     if (heavy[v] != -1) {
  71.         dfs_hld(heavy[v], v, h);
  72.     }
  73.  
  74.     for (int u : adj[v]) {
  75.         if (u != p && u != heavy[v]) {
  76.             dfs_hld(u, v, u);
  77.         }
  78.     }  
  79. }
  80. Node tree_seg[4 * MAXN];
  81.  
  82. void build(int node, int l, int r) {
  83.     if (l == r) {
  84.         tree_seg[node] = Node(arr[l]);
  85.         return;
  86.     }
  87.     int mid = (l + r) / 2;
  88.     build(2 * node, l, mid);
  89.     build(2 * node + 1, mid + 1, r);
  90.     tree_seg[node] = merge(tree_seg[2 * node], tree_seg[2 * node + 1]);
  91. }
  92.  
  93. void update(int node, int l, int r, int idx, long long val) {
  94.     if (l == r) {
  95.         tree_seg[node] = Node(val);
  96.         return;
  97.     }
  98.     int mid = (l + r) / 2;
  99.     if (idx <= mid) update(2 * node, l, mid, idx, val);
  100.     else update(2 * node + 1, mid + 1, r, idx, val);
  101.     tree_seg[node] = merge(tree_seg[2 * node], tree_seg[2 * node + 1]);
  102. }
  103.  
  104. Node query_tree(int node, int l, int r, int ql, int qr) {
  105.     if (ql <= l && r <= qr) return tree_seg[node];
  106.     int mid = (l + r) / 2;
  107.     if (qr <= mid) return query_tree(2 * node, l, mid, ql, qr);
  108.     if (ql > mid) return query_tree(2 * node + 1, mid + 1, r, ql, qr);
  109.     return merge(query_tree(2 * node, l, mid, ql, qr), query_tree(2 * node + 1, mid + 1, r, ql, qr));
  110. }
  111.  
  112. long long query_path(int u, int v) {
  113.     Node left_res, right_res; 
  114.  
  115.     while (head[u] != head[v]) {
  116.         if (depth[head[u]] >= depth[head[v]]) {
  117.             Node q_res = query_tree(1, 1, n, pos[head[u]], pos[u]);
  118.             left_res = merge(left_res, reverse_node(q_res));
  119.             u = parent_node[head[u]];
  120.         } else {
  121.             Node q_res = query_tree(1, 1, n, pos[head[v]], pos[v]);
  122.             right_res = merge(q_res, right_res);
  123.             v = parent_node[head[v]];
  124.         }
  125.     }
  126.  
  127.     if (depth[u] >= depth[v]) {
  128.         Node q_res = query_tree(1, 1, n, pos[v], pos[u]);
  129.         left_res = merge(left_res, reverse_node(q_res));
  130.     } else {
  131.         Node q_res = query_tree(1, 1, n, pos[u], pos[v]);
  132.         right_res = merge(q_res, right_res);
  133.     }
  134.  
  135.     Node final_res = merge(left_res, right_res);
  136.     return final_res.ans;
  137. }
  138.  
  139. int main() {
  140.     ios_base::sync_with_stdio(false);
  141.     cin.tie(NULL);
  142.     cout.tie(NULL);
  143.  
  144.     if (!(cin >> n >> q)) return 0;
  145.  
  146.     for (int i = 1; i <= n; i++) cin >> A[i];
  147.  
  148.     for (int i = 1; i < n; i++) {
  149.         int u, v;
  150.         cin >> u >> v;
  151.         adj[u].push_back(v);
  152.         adj[v].push_back(u);
  153.     }
  154.     dfs_sz(1, 0, 0);
  155.     dfs_hld(1, 0, 1);
  156.     build(1, 1, n);
  157.     while (q--) {
  158.         int type;
  159.         cin >> type;
  160.         if (type == 1) {
  161.             int u;
  162.             long long x;
  163.             cin >> u >> x;
  164.             update(1, 1, n, pos[u], x);
  165.         } else {
  166.             int u, v;
  167.             cin >> u >> v;
  168.             cout << query_path(u, v) << "\n";
  169.         }
  170.     }
  171.  
  172.     return 0;
  173. }
  174.  
Success #stdin #stdout 0.01s 24280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4Mur2Q
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!