fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(x) x.begin(),x.end()
  4. #define ll long long
  5. #define endl '\n'
  6. #define fi first
  7. #define se second
  8. const int N = 1e5 + 7;
  9. bool visited[N];
  10. int n, m, par[N][27], h[N];
  11. int a[N], in[N], out[N], timer;
  12. vector<int> adj[N];
  13. ll node[N], node2[N];
  14. void update(int idx, ll val, ll node[]) {
  15.     while(idx <= n) {
  16.         node[idx] += val;
  17.         idx += idx & -idx;
  18.     }
  19. }
  20. ll get(int idx, ll node[]) {
  21.     ll ans = 0;
  22.     while(idx > 0) {
  23.         ans += node[idx];
  24.         idx -= idx & -idx;
  25.     }
  26.     return ans;
  27. }
  28. void update2(int l, int r, ll val, ll node[]) {
  29.     update(l, val, node);
  30.     update(r + 1, -val, node);
  31. }
  32. void dfs(int u, int p) {
  33.     //cout << u << endl;
  34.     in[u] = ++timer;
  35.     for(auto v : adj[u]) if(v != p) {
  36.         h[v] = h[u] + 1;
  37.         par[v][0] = u;
  38.         for(int i = 1; i <= 20; i++)
  39.             par[v][i] = par[par[v][i - 1]][i - 1];
  40.         dfs(v, u);
  41.         ll val = max(abs(a[u] - a[v]), abs(a[u] + a[v]));
  42.         update2(in[v], out[v], val, node);
  43.         val = max(abs(a[v] - a[u]), abs(a[u] + a[v]));
  44.         update2(in[v], out[v], val, node2);
  45.     }
  46.     out[u] = timer;
  47. }
  48. int lca(int u, int v) {
  49.     if(h[u] < h[v]) swap(u, v);
  50.     int k = h[u] - h[v];
  51.     for(int i = 20; i >= 0; i--)
  52.         if((k >> i) & 1) u = par[u][i];
  53.     if(u == v) return u;
  54.     for(int i = 20; i >= 0; i--)
  55.         if(par[u][i] != par[v][i]) {
  56.             u = par[u][i];
  57.             v = par[v][i];
  58.         }
  59.     return par[u][0];
  60. }
  61. signed main() {
  62.     if (fopen("maze.inp", "r")) {
  63.         freopen("maze.inp", "r", stdin);
  64.         freopen("maze.out", "w", stdout);
  65.     }
  66.     if (fopen("vd.inp", "r")) {
  67.         freopen("vd.inp", "r", stdin);
  68.         freopen("vd.out", "w", stdout);
  69.     }
  70.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  71.     cin >> n >> m;
  72.     for(int i = 1; i <= n; i++) cin >> a[i];
  73.     for(int i = 1; i <= n - 1; i++) {
  74.         int u, v; cin >> u >> v;
  75.         adj[u].push_back(v);
  76.         adj[v].push_back(u);
  77.     }
  78.     dfs(1, -1);
  79.     while(m--) {
  80.         int type; cin >> type;
  81.         if(type == 1) {
  82.             int v, c; cin >> v >> c;
  83.             if(par[v][0] != 0) {
  84.                 int u = par[v][0];
  85.                 ll val = max(abs(a[u] - a[v]), abs(a[u] + a[v]));
  86.                 update2(in[v], out[v], -val, node);
  87.  
  88.                 val = max(abs(a[v] - a[u]), abs(a[u] + a[v]));
  89.                 update2(in[v], out[v], -val, node2);
  90.                 val = max(abs(a[u] - c), abs(a[u] + c));
  91.                 update2(in[v], out[v], val, node);
  92.  
  93.                 val = max(abs(c - a[u]), abs(a[u] + c));
  94.                 update2(in[v], out[v], val, node2);
  95.                 for(auto vv : adj[v]) {
  96.                     val = max(abs(c - a[vv]), abs(c + a[vv]));
  97.                     update2(in[vv], out[vv], val, node);
  98.                     val = max(abs(a[vv] - c), abs(c + a[vv]));
  99.                     update2(in[vv], out[vv], val, node2);
  100.  
  101.                     val = max(abs(a[v] - a[vv]), abs(a[v] + a[vv]));
  102.                     update2(in[vv], out[vv], -val, node);
  103.                     val = max(abs(a[vv] - a[v]), abs(a[v] + a[vv]));
  104.                     update2(in[vv], out[vv], -val, node2);
  105.                 }
  106.                 a[v] = c;
  107.             }
  108.         } else {
  109.             int u, v; cin >> u >> v;
  110.             int uv = lca(u, v);
  111.             cout << get(in[u], node2) + get(in[v], node) - get(uv, node) - get(uv, node2) << endl;
  112.         }
  113.     }
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0.01s 7908KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/O80LQC
language:
C++14 (clang 8.0)
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!