fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. static const ll NEG = -(1LL << 60);
  6.  
  7. struct Mat {
  8.     ll a[2][2];
  9. };
  10.  
  11. struct SegTree {
  12.     int n;
  13.     vector<Mat> st;
  14.     vector<ll> *val;
  15.     vector<int> *rev;
  16.  
  17.     static Mat mergeMat(const Mat &L, const Mat &R) {
  18.         Mat C;
  19.         for (int i = 0; i < 2; ++i)
  20.             for (int j = 0; j < 2; ++j)
  21.                 C.a[i][j] = NEG;
  22.  
  23.         for (int lf = 0; lf < 2; ++lf) {
  24.             for (int llv = 0; llv < 2; ++llv) {
  25.                 if (L.a[lf][llv] == NEG) continue;
  26.                 for (int rf = 0; rf < 2; ++rf) {
  27.                     if (R.a[rf][0] == NEG && R.a[rf][1] == NEG) continue;
  28.                     if (llv == 1 && rf == 1) continue;
  29.                     for (int rl = 0; rl < 2; ++rl) {
  30.                         if (R.a[rf][rl] == NEG) continue;
  31.                         C.a[lf][rl] = max(C.a[lf][rl], L.a[lf][llv] + R.a[rf][rl]);
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.         return C;
  37.     }
  38.  
  39.     static Mat leaf(ll x) {
  40.         Mat m;
  41.         for (int i = 0; i < 2; ++i)
  42.             for (int j = 0; j < 2; ++j)
  43.                 m.a[i][j] = NEG;
  44.         m.a[0][0] = 0;
  45.         m.a[1][1] = x;
  46.         return m;
  47.     }
  48.  
  49.     void build(int idx, int l, int r) {
  50.         if (l == r) {
  51.             st[idx] = leaf((*val)[(*rev)[l]]);
  52.             return;
  53.         }
  54.         int mid = (l + r) >> 1;
  55.         build(idx << 1, l, mid);
  56.         build(idx << 1 | 1, mid + 1, r);
  57.         st[idx] = mergeMat(st[idx << 1], st[idx << 1 | 1]);
  58.     }
  59.  
  60.     SegTree() {}
  61.     SegTree(int n, vector<ll> *val, vector<int> *rev) : n(n), val(val), rev(rev) {
  62.         st.resize(4 * n + 5);
  63.         build(1, 1, n);
  64.     }
  65.  
  66.     void update(int idx, int l, int r, int pos) {
  67.         if (l == r) {
  68.             st[idx] = leaf((*val)[(*rev)[l]]);
  69.             return;
  70.         }
  71.         int mid = (l + r) >> 1;
  72.         if (pos <= mid) update(idx << 1, l, mid, pos);
  73.         else update(idx << 1 | 1, mid + 1, r, pos);
  74.         st[idx] = mergeMat(st[idx << 1], st[idx << 1 | 1]);
  75.     }
  76.  
  77.     Mat query(int idx, int l, int r, int ql, int qr) {
  78.         if (qr < l || r < ql) {
  79.             Mat bad;
  80.             for (int i = 0; i < 2; ++i)
  81.                 for (int j = 0; j < 2; ++j)
  82.                     bad.a[i][j] = NEG;
  83.             return bad;
  84.         }
  85.         if (ql <= l && r <= qr) return st[idx];
  86.         int mid = (l + r) >> 1;
  87.         Mat L = query(idx << 1, l, mid, ql, qr);
  88.         Mat R = query(idx << 1 | 1, mid + 1, r, ql, qr);
  89.  
  90.         if (L.a[0][0] == NEG && L.a[0][1] == NEG && L.a[1][0] == NEG && L.a[1][1] == NEG) return R;
  91.         if (R.a[0][0] == NEG && R.a[0][1] == NEG && R.a[1][0] == NEG && R.a[1][1] == NEG) return L;
  92.         return mergeMat(L, R);
  93.     }
  94. };
  95.  
  96. int main() {
  97.     ios::sync_with_stdio(false);
  98.     cin.tie(nullptr);
  99.  
  100.     int n, q;
  101.     cin >> n >> q;
  102.  
  103.     vector<ll> a(n + 1);
  104.     for (int i = 1; i <= n; ++i) cin >> a[i];
  105.  
  106.     vector<vector<int>> g(n + 1);
  107.     for (int i = 1; i <= n - 1; ++i) {
  108.         int u, v;
  109.         cin >> u >> v;
  110.         g[u].push_back(v);
  111.         g[v].push_back(u);
  112.     }
  113.  
  114.     vector<int> parent(n + 1, 0), depth(n + 1, 0), heavy(n + 1, -1), sz(n + 1, 0);
  115.     vector<int> order;
  116.     order.reserve(n);
  117.  
  118.     stack<int> st;
  119.     st.push(1);
  120.     parent[1] = 0;
  121.     depth[1] = 0;
  122.  
  123.     while (!st.empty()) {
  124.         int u = st.top();
  125.         st.pop();
  126.         order.push_back(u);
  127.         for (int v : g[u]) {
  128.             if (v == parent[u]) continue;
  129.             parent[v] = u;
  130.             depth[v] = depth[u] + 1;
  131.             st.push(v);
  132.         }
  133.     }
  134.  
  135.     for (int i = n - 1; i >= 0; --i) {
  136.         int u = order[i];
  137.         sz[u] = 1;
  138.         int best = -1;
  139.         for (int v : g[u]) {
  140.             if (v == parent[u]) continue;
  141.             sz[u] += sz[v];
  142.             if (best == -1 || sz[v] > sz[best]) best = v;
  143.         }
  144.         heavy[u] = best;
  145.     }
  146.  
  147.     vector<int> head(n + 1, 0), pos(n + 1, 0), rev(n + 1, 0);
  148.     int cur = 0;
  149.     vector<pair<int,int>> chains;
  150.     chains.push_back({1, 1});
  151.  
  152.     while (!chains.empty()) {
  153.         auto [u, h] = chains.back();
  154.         chains.pop_back();
  155.  
  156.         for (int v = u; v != -1; v = heavy[v]) {
  157.             head[v] = h;
  158.             pos[v] = ++cur;
  159.             rev[cur] = v;
  160.  
  161.             for (int to : g[v]) {
  162.                 if (to == parent[v] || to == heavy[v]) continue;
  163.                 chains.push_back({to, to});
  164.             }
  165.         }
  166.     }
  167.  
  168.     SegTree seg(cur, &a, &rev);
  169.  
  170.     auto revMat = [&](const Mat &m) {
  171.         Mat t;
  172.         t.a[0][0] = m.a[0][0];
  173.         t.a[0][1] = m.a[1][0];
  174.         t.a[1][0] = m.a[0][1];
  175.         t.a[1][1] = m.a[1][1];
  176.         return t;
  177.     };
  178.  
  179.     auto queryRange = [&](int l, int r) {
  180.         return seg.query(1, 1, cur, l, r);
  181.     };
  182.  
  183.     auto pathQuery = [&](int u, int v) {
  184.         vector<Mat> rightParts;
  185.         Mat ans;
  186.         bool has = false;
  187.  
  188.         while (head[u] != head[v]) {
  189.             if (depth[head[u]] >= depth[head[v]]) {
  190.                 Mat curMat = queryRange(pos[head[u]], pos[u]);
  191.                 curMat = revMat(curMat);
  192.                 if (!has) {
  193.                     ans = curMat;
  194.                     has = true;
  195.                 } else {
  196.                     ans = SegTree::mergeMat(ans, curMat);
  197.                 }
  198.                 u = parent[head[u]];
  199.             } else {
  200.                 Mat curMat = queryRange(pos[head[v]], pos[v]);
  201.                 rightParts.push_back(curMat);
  202.                 v = parent[head[v]];
  203.             }
  204.         }
  205.  
  206.         if (depth[u] >= depth[v]) {
  207.             Mat curMat = queryRange(pos[v], pos[u]);
  208.             curMat = revMat(curMat);
  209.             if (!has) {
  210.                 ans = curMat;
  211.                 has = true;
  212.             } else {
  213.                 ans = SegTree::mergeMat(ans, curMat);
  214.             }
  215.         } else {
  216.             Mat curMat = queryRange(pos[u], pos[v]);
  217.             rightParts.push_back(curMat);
  218.         }
  219.  
  220.         for (int i = (int)rightParts.size() - 1; i >= 0; --i) {
  221.             if (!has) {
  222.                 ans = rightParts[i];
  223.                 has = true;
  224.             } else {
  225.                 ans = SegTree::mergeMat(ans, rightParts[i]);
  226.             }
  227.         }
  228.  
  229.         ll best = 0;
  230.         for (int i = 0; i < 2; ++i)
  231.             for (int j = 0; j < 2; ++j)
  232.                 best = max(best, ans.a[i][j]);
  233.         return best;
  234.     };
  235.  
  236.     while (q--) {
  237.         int type;
  238.         cin >> type;
  239.         if (type == 1) {
  240.             int x;
  241.             ll y;
  242.             cin >> x >> y;
  243.             a[x] = y;
  244.             seg.update(1, 1, cur, pos[x]);
  245.         } else {
  246.             int u, v;
  247.             cin >> u >> v;
  248.             cout << pathQuery(u, v) << '\n';
  249.         }
  250.     }
  251.  
  252.     return 0;
  253. }
  254.  
Runtime error #stdin #stdout 0.04s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/IQcqv1
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
secret

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!