fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define fi first
  5. #define se second
  6. #define pii pair<int, int>
  7. #define all(x) (x).begin(), (x).end()
  8. using namespace std;
  9.  
  10. const int N = 1e5 + 5;
  11. int h[N], sz[N], par[N], chainId[N], head[N], curChain = 1, pos[N], curPos = 0, n, q, a[N];
  12. vector<int> ad[N];
  13.  
  14. void dfs(int u, int p)
  15. {
  16.     sz[u] = 1;
  17.     for (int v : ad[u])
  18.     {
  19.         if (v == p) continue;
  20.         h[v] = h[u] + 1;
  21.         par[v] = u;
  22.         dfs(v, u);
  23.         sz[u] += sz[v];
  24.     }
  25. }
  26.  
  27. void hld(int u, int p)
  28. {
  29.     if (!head[curChain]) head[curChain] = u;
  30.     chainId[u] = curChain;
  31.     pos[u] = ++curPos;
  32.     int nxt = -1;
  33.     for (int v : ad[u])
  34.     {
  35.         if (v == p) continue;
  36.         if (nxt == -1 || sz[v] > sz[nxt]) nxt = v;
  37.     }
  38.     if (nxt != -1) hld(nxt, u);
  39.     for (int v : ad[u])
  40.     {
  41.         if (v == p || v == nxt) continue;
  42.         curChain++;
  43.         hld(v, u);
  44.     }
  45. }
  46.  
  47. int lca(int u, int v)
  48. {
  49.     while (chainId[u] != chainId[v])
  50.     {
  51.         if (chainId[u] > chainId[v]) u = par[head[chainId[u]]];
  52.         else v = par[head[chainId[v]]];
  53.     }
  54.     if (h[u] < h[v]) return u;
  55.     return v;
  56. }
  57.  
  58. const ll INF = 1e18;
  59. struct Node
  60. {
  61.     ll sum, pre, suf, mx;
  62. } st[4*N];
  63. ll lz[4*N];
  64.  
  65. Node merge(const Node &l, const Node &r)
  66. {
  67.     Node res;
  68.     res.sum = l.sum + r.sum;
  69.     res.pre = max(l.pre, l.sum+r.pre);
  70.     res.suf = max(r.suf, r.sum+l.suf);
  71.     res.mx = max({l.mx, r.mx, l.suf+r.pre});
  72.     return res;
  73. }
  74.  
  75. void build(int id, int l, int r)
  76. {
  77.     st[id] = {0, 0, 0, 0};
  78.     lz[id] = INF;
  79.     if (l == r) return;
  80.     int mid = (l+r)/2;
  81.     build(2*id, l, mid);
  82.     build(2*id+1, mid+1, r);
  83. }
  84.  
  85. void apply(int id, int l, int r, ll x)
  86. {
  87.     lz[id] = x;
  88.     if (x < 0) st[id] = {x*(r-l+1), 0, 0, 0};
  89.     else st[id] = {x*(r-l+1), x*(r-l+1), x*(r-l+1), x*(r-l+1)};
  90. }
  91.  
  92. void push(int id, int l, int mid, int r)
  93. {
  94.     if (lz[id] == INF) return;
  95.     apply(2*id, l, mid, lz[id]);
  96.     apply(2*id+1, mid+1, r, lz[id]);
  97.     lz[id] = INF;
  98. }
  99.  
  100. void upd(int id, int l, int r, int u, int v, ll x)
  101. {
  102.     if (v < l || r < u) return;
  103.     if (u <= l && r <= v)
  104.     {
  105.         apply(id, l, r, x);
  106.         return;
  107.     }
  108.     int mid = (l+r)/2;
  109.     push(id, l, mid, r);
  110.     upd(2*id, l, mid, u, v, x);
  111.     upd(2*id+1, mid+1, r, u, v, x);
  112.     st[id] = merge(st[2*id], st[2*id+1]);
  113. }
  114.  
  115. Node get(int id, int l, int r, int u, int v)
  116. {
  117.     if (v < l || r < u || u > v) return {0, 0, 0, 0};
  118.     if (u <= l && r <= v) return st[id];
  119.     int mid = (l+r)/2;
  120.     push(id, l, mid, r);
  121.     return merge(get(2*id, l, mid, u, v), get(2*id+1, mid+1, r, u, v));
  122. }
  123.  
  124. int main()
  125. {
  126.     ios_base::sync_with_stdio(false);
  127.     cin.tie(NULL);
  128.     #define task ""
  129.     if (fopen(task".inp", "r"))
  130.     {
  131.         freopen(task".inp", "r", stdin);
  132.         freopen(task".out", "w", stdout);
  133.     }
  134.  
  135.     cin >> n;
  136.     for (int i = 1; i <= n; i++) cin >> a[i];
  137.     for (int i = 1; i < n; i++)
  138.     {
  139.         int u, v; cin >> u >> v;
  140.         ad[u].push_back(v);
  141.         ad[v].push_back(u);
  142.     }
  143.     dfs(1, 0);
  144.     hld(1, 0);
  145.     for (int i = 1; i <= n; i++) upd(1, 1, n, pos[i], pos[i], a[i]);
  146.     cin >> q;
  147.     while (q--)
  148.     {
  149.         int t; cin >> t;
  150.         if (t == 1)
  151.         {
  152.             int u, v; cin >> u >> v;
  153.             int w = lca(u, v);
  154.             Node l = {0, 0, 0, 0};
  155.             while (chainId[u] != chainId[w])
  156.             {
  157.                 l = merge(get(1, 1, n, pos[head[chainId[u]]], pos[u]), l);
  158.                 u = par[head[chainId[u]]];
  159.             }
  160.             l = merge(get(1, 1, n, pos[w], pos[u]), l);
  161.             Node r = {0, 0, 0, 0};
  162.             while (chainId[v] != chainId[w])
  163.             {
  164.                 r = merge(get(1, 1, n, pos[head[chainId[v]]], pos[v]), r);
  165.                 v = par[head[chainId[v]]];
  166.             }
  167.             r = merge(get(1, 1, n, pos[w]+1, pos[v]), r);
  168.             swap(l.pre, l.suf);
  169.             l = merge(l, r);
  170.             cout << l.mx << '\n';
  171.         }
  172.         else
  173.         {
  174.             int u, v; ll c; cin >> u >> v >> c;
  175.             int w = lca(u, v);
  176.             while (chainId[u] != chainId[w])
  177.             {
  178.                 upd(1, 1, n, pos[head[chainId[u]]], pos[u], c);
  179.                 u = par[head[chainId[u]]];
  180.             }
  181.             upd(1, 1, n, pos[w], pos[u], c);
  182.             while (chainId[v] != chainId[w])
  183.             {
  184.                 upd(1, 1, n, pos[head[chainId[v]]], pos[v], c);
  185.                 v = par[head[chainId[v]]];
  186.             }
  187.             upd(1, 1, n, pos[w]+1, pos[v], c);
  188.         }
  189.     }
  190.  
  191.     return 0;
  192. }
  193.  
Success #stdin #stdout 0.01s 7792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eyoJZg
language:
C++14 (gcc 8.3)
created:
1 day 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!