fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. const int MAXN = 2e5 + 7;
  6. const ll INF = 1e18;
  7.  
  8. struct Node {
  9.     ll sum, pre, suf, ma;
  10.     Node() : sum(0), pre(-INF), suf(-INF), ma(-INF) {}
  11.     Node(ll val) : sum(val), pre(val), suf(val), ma(val) {}
  12. };
  13.  
  14. Node merge(const Node& a, const Node& b) {
  15.     Node res;
  16.     res.sum = a.sum + b.sum;
  17.     res.pre = max(a.pre, a.sum + b.pre);
  18.     res.suf = max(b.suf, a.suf + b.sum);
  19.     res.ma = max({a.ma, b.ma, a.suf + b.pre});
  20.     return res;
  21. }
  22.  
  23. struct SegmentTree {
  24.     vector<Node> t;
  25.     vector<ll> lazy;
  26.     int n;
  27.  
  28.     SegmentTree(int size) {
  29.         n = size;
  30.         t.resize(4 * n + 7);
  31.         lazy.resize(4 * n + 7, INF);
  32.     }
  33.  
  34.     void push(int id, int l, int r) {
  35.         if (lazy[id] == INF) return;
  36.         ll x = lazy[id];
  37.         t[id] = Node(x * (r - l + 1));
  38.         if (l != r) {
  39.             lazy[2 * id] = x;
  40.             lazy[2 * id + 1] = x;
  41.         }
  42.         lazy[id] = INF;
  43.     }
  44.  
  45.     void build(int id, int l, int r, const vector<ll>& a) {
  46.         if (l == r) {
  47.             t[id] = Node(a[l]);
  48.             return;
  49.         }
  50.         int mid = (l + r) / 2;
  51.         build(2 * id, l, mid, a);
  52.         build(2 * id + 1, mid + 1, r, a);
  53.         t[id] = merge(t[2 * id], t[2 * id + 1]);
  54.     }
  55.  
  56.     void update(int id, int l, int r, int u, int v, ll x) {
  57.         push(id, l, r);
  58.         if (v < l || r < u) return;
  59.         if (u <= l && r <= v) {
  60.             lazy[id] = x;
  61.             push(id, l, r);
  62.             return;
  63.         }
  64.         int mid = (l + r) / 2;
  65.         update(2 * id, l, mid, u, v, x);
  66.         update(2 * id + 1, mid + 1, r, u, v, x);
  67.         t[id] = merge(t[2 * id], t[2 * id + 1]);
  68.     }
  69.  
  70.     Node query(int id, int l, int r, int u, int v) {
  71.         push(id, l, r);
  72.         if (v < l || r < u) return Node();
  73.         if (u <= l && r <= v) return t[id];
  74.         int mid = (l + r) / 2;
  75.         return merge(query(2 * id, l, mid, u, v), 
  76.                     query(2 * id + 1, mid + 1, r, u, v));
  77.     }
  78. };
  79.  
  80. struct HLD {
  81.     int n;
  82.     vector<int> parent, depth, heavy, head, pos;
  83.     vector<vector<int>> adj;
  84.     int cur_pos;
  85.     SegmentTree st;
  86.  
  87.     HLD(int n) : n(n), st(n), parent(n+1), depth(n+1), 
  88.                 heavy(n+1, -1), head(n+1), pos(n+1), adj(n+1), cur_pos(0) {}
  89.  
  90.     void add_edge(int u, int v) {
  91.         adj[u].push_back(v);
  92.         adj[v].push_back(u);
  93.     }
  94.  
  95.     int dfs(int v) {
  96.         int size = 1;
  97.         int max_c_size = 0;
  98.         for (int c : adj[v]) {
  99.             if (c != parent[v]) {
  100.                 parent[c] = v;
  101.                 depth[c] = depth[v] + 1;
  102.                 int c_size = dfs(c);
  103.                 size += c_size;
  104.                 if (c_size > max_c_size) {
  105.                     max_c_size = c_size;
  106.                     heavy[v] = c;
  107.                 }
  108.             }
  109.         }
  110.         return size;
  111.     }
  112.  
  113.     void decompose(int v, int h) {
  114.         head[v] = h;
  115.         pos[v] = cur_pos++;
  116.         if (heavy[v] != -1)
  117.             decompose(heavy[v], h);
  118.         for (int c : adj[v]) {
  119.             if (c != parent[v] && c != heavy[v])
  120.                 decompose(c, c);
  121.         }
  122.     }
  123.  
  124.     void init(vector<ll>& a) {
  125.         dfs(1);
  126.         decompose(1, 1);
  127.         vector<ll> arr(n);
  128.         for (int i = 1; i <= n; i++)
  129.             arr[pos[i]] = a[i];
  130.         st.build(1, 0, n-1, arr);
  131.     }
  132.  
  133.     void update_path(int u, int v, ll x) {
  134.         for (; head[u] != head[v]; v = parent[head[v]]) {
  135.             if (depth[head[u]] > depth[head[v]]) swap(u, v);
  136.             st.update(1, 0, n-1, pos[head[v]], pos[v], x);
  137.         }
  138.         if (depth[u] > depth[v]) swap(u, v);
  139.         st.update(1, 0, n-1, pos[u], pos[v], x);
  140.     }
  141.  
  142.     Node query_path(int u, int v) {
  143.         Node res;
  144.         bool first = true;
  145.         for (; head[u] != head[v]; v = parent[head[v]]) {
  146.             if (depth[head[u]] > depth[head[v]]) swap(u, v);
  147.             Node cur = st.query(1, 0, n-1, pos[head[v]], pos[v]);
  148.             if (first) {
  149.                 res = cur;
  150.                 first = false;
  151.             } else {
  152.                 res = merge(cur, res);
  153.             }
  154.         }
  155.         if (depth[u] > depth[v]) swap(u, v);
  156.         Node last = st.query(1, 0, n-1, pos[u], pos[v]);
  157.         if (first) return last;
  158.         return merge(last, res);
  159.     }
  160. };
  161.  
  162. int main() {
  163.     ios_base::sync_with_stdio(false);
  164.     cin.tie(nullptr);
  165.  
  166.     int n, q;
  167.     cin >> n >> q;
  168.     vector<ll> a(n+1);
  169.     for (int i = 1; i <= n; i++) cin >> a[i];
  170.  
  171.     HLD hld(n);
  172.     for (int i = 1; i < n; i++) {
  173.         int u, v;
  174.         cin >> u >> v;
  175.         hld.add_edge(u, v);
  176.     }
  177.  
  178.     hld.init(a);
  179.  
  180.     while (q--) {
  181.         int type, u, v;
  182.         cin >> type >> u >> v;
  183.         if (type == 1) {
  184.             Node res = hld.query_path(u, v);
  185.             cout << max(0LL, res.ma) << "\n";
  186.         } else {
  187.             ll x;
  188.             cin >> x;
  189.             hld.update_path(u, v, x);
  190.         }
  191.     }
  192.  
  193.     return 0;
  194. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5 3
-3 -2 1 2 3
1 2
2 3
1 4
4 5
1 2 5
2 3 4 2
1 2 5
stdout
copy 
5
9
https://ideone.com/tWiu1X
language:
C++14 (gcc 8.3)
created:
15 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!