fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pii pair<int,int>
  7. #define pll pair<ll,ll>
  8. #define FOR(i,k,n) for ( int i = (k),_n=(n); i<=_n; i++)
  9. #define FOD(i,k,n) for ( int i = (k),_n=(n); i>=_n; i--)
  10. #define pb push_back
  11. const int maxn =1e5+5;
  12. ll chain=0,cnt=0;
  13. vector<int>a[maxn];
  14. ll wi[maxn],sz[maxn],pa[maxn],s[4*maxn],lz[4*maxn],pos[maxn],arr[maxn],h[maxn],head[maxn],id[maxn];
  15. int n,t;
  16.  
  17. void buildt(int id, int l, int r){
  18.     if (l > r) return;
  19.     if (l == r) {
  20.         s[id] = wi[arr[l]];
  21.         return;
  22.     }
  23.     int mid = (l + r) / 2;
  24.     buildt(2 * id, l, mid);
  25.     buildt(2 * id + 1, mid + 1, r);
  26.     s[id] = s[2 * id] + s[2 * id + 1];
  27. }
  28.  
  29. void pus(int id, int l, int r){
  30.     if (lz[id]){
  31.         s[id] += (r - l + 1) * lz[id];
  32.         if (l != r){
  33.             lz[2 * id] += lz[id];
  34.             lz[2 * id + 1] += lz[id];
  35.         }
  36.         lz[id] = 0;
  37.     }
  38. }
  39.  
  40. void update(int id, int l, int r, int u, int v, ll w){
  41.     pus(id, l, r);
  42.     if (l > v || r < u) return;
  43.     if (l >= u && r <= v){
  44.         lz[id] += w;
  45.         pus(id, l, r);
  46.         return;
  47.     }
  48.     int mid = (l + r) / 2;
  49.     update(2 * id, l, mid, u, v, w);
  50.     update(2 * id + 1, mid + 1, r, u, v, w);
  51.     s[id] = s[2 * id] + s[2 * id + 1];
  52. }
  53.  
  54. ll get(int id, int l, int r, int u, int v){
  55.     pus(id, l, r);
  56.     if (l > v || r < u) return 0;
  57.     if (l >= u && r <= v) return s[id];
  58.     int mid = (l + r) / 2;
  59.     return get(2 * id, l, mid, u, v) + get(2 * id + 1, mid + 1, r, u, v);
  60. }
  61.  
  62. void dfs(int u, int p){
  63.     sz[u] = 1;
  64.     for (int v : a[u]) if (v != p){
  65.         pa[v] = u;
  66.         h[v] = h[u] + 1;
  67.         dfs(v, u);
  68.         sz[u] += sz[v];
  69.     }
  70. }
  71.  
  72. void hld(int u, int p){
  73.     if (!head[chain]) head[chain] = u;
  74.     pos[u] = ++cnt;
  75.     id[u] = chain;
  76.     arr[cnt] = u;
  77.     int mx = 0;
  78.     for (int v : a[u]) if (v != p && sz[v] > sz[mx]) mx = v;
  79.     if (mx) hld(mx, u);
  80.     for (int v : a[u]) if (v != p && v != mx){
  81.         chain++;
  82.         hld(v, u);
  83.     }
  84. }
  85.  
  86. void updhld(int u, int v, ll w){
  87.     while (id[u] != id[v]){
  88.         if (h[head[id[u]]] < h[head[id[v]]]) swap(u, v);
  89.         update(1, 1, n, pos[head[id[u]]], pos[u], w);
  90.         u = pa[head[id[u]]];
  91.     }
  92.     if (h[u] > h[v]) swap(u, v);
  93.     update(1, 1, n, pos[u], pos[v], w);
  94. }
  95.  
  96. ll query(int u, int v){
  97.     ll res = 0;
  98.     while (id[u] != id[v]){
  99.         if (h[head[id[u]]] < h[head[id[v]]]) swap(u, v);
  100.         res += get(1, 1, n, pos[head[id[u]]], pos[u]);
  101.         u = pa[head[id[u]]];
  102.     }
  103.     if (h[u] > h[v]) swap(u, v);
  104.     res += get(1, 1, n, pos[u], pos[v]);
  105.     return res;
  106. }
  107.  
  108. int main(){
  109.     ios_base::sync_with_stdio(false);
  110.     cin.tie(NULL);
  111.     cout.tie(NULL);
  112.     cin >> n >> t;
  113.     FOR(i, 1, n) cin >> wi[i];
  114.     FOR(i, 1, n - 1){
  115.         int u, v;
  116.         cin >> u >> v;
  117.         a[u].pb(v);
  118.         a[v].pb(u);
  119.     }
  120.     dfs(1, 1);
  121.     hld(1, 1);
  122.     buildt(1, 1, n);
  123.     while (t--){
  124.         int type;
  125.         cin >> type;
  126.         if (type == 1){
  127.             int u, v;
  128.             ll w;
  129.             cin >> u >> v >> w;
  130.             updhld(u, v, w);
  131.         } else {
  132.             int u, v;
  133.             cin >> u >> v;
  134.             cout << query(u, v) << endl;
  135.         }
  136.     }
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0.01s 10484KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/I49QA7
language:
C++14 (gcc 8.3)
created:
7 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!