code/graphs/LCABLW.cc

View this file on GitHub
Last update: 2020-10-28 23:44:21+01:00

Depends on

code/template.cc

Code

#include "../template.hh"

template <typename T, typename F>
struct LCA {
  int n, logN, root, e;
  F f;
  vvi up;
  vector<vector<T>> weight;
  vi h;
  LCA(vector<vector<pair<int, T>>>& adj, F _f, T _e, int r = 0)
      : n{SZ(adj)}, logN{31 - __builtin_clz(n)},
        root{r}, e{_e}, f{_f},
        up(n, vi(logN + 1, root)), 
        weight(n, vector<T>(logN + 1, _e)), h(n, -1) { 
    build(adj);
  }
  void build(vector<vector<pair<int, T>>>& adj) {
    queue<int> q;
    q.push(root);
    h[root] = 0;
    while (SZ(q)) {
      int v = q.front();
      q.pop();
      for (auto [u, w] : adj[v])
        if (h[u] == -1) {
          h[u] = h[v] + 1;
          q.push(u);
          up[u][0] = v;
          weight[u][0] = w;
        }
    }
    FOR (exp, 1, logN + 1)
      F0R (v, n)
        if (up[v][exp - 1] != -1) {
          up[v][exp] = up[up[v][exp - 1]][exp - 1];
          weight[v][exp] = f(weight[v][exp - 1], 
                             weight[up[v][exp - 1]][exp - 1]);
        }
  }
  int jumpUp(int v, int amt) {
    for (int i = 0; v != -1 && (1 << i) <= amt; ++i)
      if (amt & (1 << i)) 
        v = up[v][i];
    return v;
  }
  int query(int v, int u) {
    v = jumpUp(v, max(0, h[v] - h[u]));
    u = jumpUp(u, max(0, h[u] - h[v]));
    if (u == v) return u;
    for (int l = logN; ~l; --l) {
      int jmpU = up[u][l], jmpV = up[v][l];
      if (jmpU == -1 || jmpV == -1) continue;
      if (jmpU != jmpV) {
        u = jmpU;
        v = jmpV;
      }
    }
    return up[v][0];
  }
  int pathQuery(int v, int u) {
    int anc = query(v, u);
    return f(pathQueryAnc(v, anc), pathQueryAnc(u, anc));
  }
  int pathQueryAnc(int v, int u) {
    int res = e;
    for (int l = logN; ~l; --l) {
      if (up[v][l] != -1 && h[u] <= h[up[v][l]]) {
        res = f(res, weight[v][l]);
        v = up[v][l];
      }
    }
    return res;
  }
};

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/LCABLW.cc"

template <typename T, typename F>
struct LCA {
  int n, logN, root, e;
  F f;
  vvi up;
  vector<vector<T>> weight;
  vi h;
  LCA(vector<vector<pair<int, T>>>& adj, F _f, T _e, int r = 0)
      : n{SZ(adj)}, logN{31 - __builtin_clz(n)},
        root{r}, e{_e}, f{_f},
        up(n, vi(logN + 1, root)), 
        weight(n, vector<T>(logN + 1, _e)), h(n, -1) { 
    build(adj);
  }
  void build(vector<vector<pair<int, T>>>& adj) {
    queue<int> q;
    q.push(root);
    h[root] = 0;
    while (SZ(q)) {
      int v = q.front();
      q.pop();
      for (auto [u, w] : adj[v])
        if (h[u] == -1) {
          h[u] = h[v] + 1;
          q.push(u);
          up[u][0] = v;
          weight[u][0] = w;
        }
    }
    FOR (exp, 1, logN + 1)
      F0R (v, n)
        if (up[v][exp - 1] != -1) {
          up[v][exp] = up[up[v][exp - 1]][exp - 1];
          weight[v][exp] = f(weight[v][exp - 1], 
                             weight[up[v][exp - 1]][exp - 1]);
        }
  }
  int jumpUp(int v, int amt) {
    for (int i = 0; v != -1 && (1 << i) <= amt; ++i)
      if (amt & (1 << i)) 
        v = up[v][i];
    return v;
  }
  int query(int v, int u) {
    v = jumpUp(v, max(0, h[v] - h[u]));
    u = jumpUp(u, max(0, h[u] - h[v]));
    if (u == v) return u;
    for (int l = logN; ~l; --l) {
      int jmpU = up[u][l], jmpV = up[v][l];
      if (jmpU == -1 || jmpV == -1) continue;
      if (jmpU != jmpV) {
        u = jmpU;
        v = jmpV;
      }
    }
    return up[v][0];
  }
  int pathQuery(int v, int u) {
    int anc = query(v, u);
    return f(pathQueryAnc(v, anc), pathQueryAnc(u, anc));
  }
  int pathQueryAnc(int v, int u) {
    int res = e;
    for (int l = logN; ~l; --l) {
      if (up[v][l] != -1 && h[u] <= h[up[v][l]]) {
        res = f(res, weight[v][l]);
        v = up[v][l];
      }
    }
    return res;
  }
};