Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:warning: test/atcoder/abc133_f.Patricia.test.cpp

Depends on

Code

// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc133/tasks/abc133_f
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 256
// 永続配列(at) の verify

#include <iostream>
#include <vector>
#include "src/DataStructure/SegmentTree_Patricia.hpp"
#include "src/Graph/Graph.hpp"
#include "src/Graph/HeavyLightDecomposition.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 Graph g(N, N - 1);
 vector<int> c(N - 1), d(N - 1);
 for (int i= 0; i < N - 1; ++i) cin >> g[i] >> c[i] >> d[i], --g[i];
 HeavyLightDecomposition hld(g, 0);
 using PerArr= SegmentTree_Patricia<int, true, 17>;
 vector<PerArr> Arr1(N), Arr2(N);
 vector<int> dep(N);
 auto adj= g.adjacency_edge(0);
 for (int i= 0; i < N; ++i) {
  int v= hld.to_vertex(i), p= hld.parent(v);
  for (int e: adj[v]) {
   int u= g[e].to(v);
   if (u == p) continue;
   Arr1[u]= Arr1[v], Arr2[u]= Arr2[v];
   Arr1[u][c[e]]+= 1, Arr2[u][c[e]]+= d[e];
   dep[u]= dep[v] + d[e];
  }
 }
 for (int i= 0; i < Q; i++) {
  int x, y, u, v;
  cin >> x >> y >> u >> v;
  int lca= hld.lca(--u, --v);
  cout << dep[u] + dep[v] - 2 * dep[lca] + y * (Arr1[u].get(x) + Arr1[v].get(x) - 2 * Arr1[lca].get(x)) - (Arr2[u].get(x) + Arr2[v].get(x) - 2 * Arr2[lca].get(x)) << '\n';
 }
 return 0;
}
#line 1 "test/atcoder/abc133_f.Patricia.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc133/tasks/abc133_f
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 256
// 永続配列(at) の verify

#include <iostream>
#include <vector>
#line 2 "src/DataStructure/SegmentTree_Patricia.hpp"
#include <array>
#line 4 "src/DataStructure/SegmentTree_Patricia.hpp"
#include <string>
#include <algorithm>
#include <tuple>
#include <cstddef>
#include <cstdint>
#line 2 "src/Internal/HAS_CHECK.hpp"
#include <type_traits>
#define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \
 template <class tClass> struct name##member { \
  template <class U, Dummy> static type1 check(U *); \
  static type2 check(...); \
  static tClass *mClass; \
  last; \
 }
#define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value)
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member)
#define HOGE_OR(member, name, type2) \
 MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \
 template <class tClass> using name##member##_t= typename name##member<tClass>::type
#define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t)
#define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass)
#line 10 "src/DataStructure/SegmentTree_Patricia.hpp"
template <typename M, bool persistent= false, uint8_t HEIGHT= 31> class SegmentTree_Patricia {
 HAS_MEMBER(op);
 HAS_MEMBER(ti);
 HAS_TYPE(T);
 template <class L> static constexpr bool monoid_v= std::conjunction_v<has_T<L>, has_op<L>, has_ti<L>>;
 using id_t= long long;
 template <class T, class tDerived> struct Node_B {
  id_t bits;
  uint8_t len;
  T val;
  tDerived *ch[2]= {nullptr, nullptr};
 };
 template <bool mo, typename tEnable= void> struct Node_D: Node_B<M, Node_D<mo, tEnable>> {};
 template <bool mo> struct Node_D<mo, typename std::enable_if_t<mo>>: Node_B<typename M::T, Node_D<mo>> {};
 using Node= Node_D<monoid_v<M>>;
 using T= decltype(Node::val);
 using np= Node *;
 np root;
 static inline constexpr T def_val() {
  if constexpr (monoid_v<M>) return M::ti();
  else return T();
 }
 template <class S> np build(const id_t &n, id_t l, id_t r, const S &bg) {
  if (n <= l) return nullptr;
  id_t m= (l + r) / 2;
  while (n <= m) r= m, m= (l + r) / 2;
  if (r - l == 1) {
   if constexpr (std::is_same_v<S, T>) return new Node{l, HEIGHT + 1, bg};
   else return new Node{l, HEIGHT + 1, *(bg + l)};
  }
  uint8_t h= __builtin_ctzll(r - l);
  np t= new Node{m >> h, uint8_t(HEIGHT + 1 - h), def_val(), {build(n, l, m, bg), build(n, m, r, bg)}};
  if constexpr (monoid_v<M>) t->val= M::op(t->ch[0]->val, t->ch[1]->val);
  return t;
 }
 void dump(np t, const id_t &l, const id_t &r, std::array<id_t, 2> b, typename std::vector<T>::iterator itr, uint8_t h) {
  if (r <= b[0] || b[1] <= l) return;
  if (l <= b[0] && b[1] <= r && !t) {
   for (id_t i= b[0]; i < b[1]; i++) *(itr + i)= def_val();
  } else if (b[1] - b[0] != 1) {
   auto m= (b[0] + b[1]) >> 1;
   dump(next(t, h, 0), l, r, {b[0], m}, itr, h - 1);
   dump(next(t, h, 1), l, r, {m, b[1]}, itr, h - 1);
  } else *(itr + b[0])= t->val;
 }
 T prod(np &t, const id_t &l, const id_t &r, const id_t &bias) {
  static id_t bits, b[2];
  if (!t) return def_val();
  uint8_t h= (HEIGHT + 1) - t->len;
  bits= (bias >> h) ^ t->bits, b[0]= bits << h, b[1]= (bits + 1) << h;
  if (r <= b[0] || b[1] <= l) return def_val();
  if (l <= b[0] && b[1] <= r) return t->val;
  bool flg= (bias >> (h - 1)) & 1;
  return M::op(prod(t->ch[flg], l, r, bias), prod(t->ch[!flg], l, r, bias));
 }
 void set_val(np &t, const id_t &k, const T &val) {
  if (!t) return t= new Node{k, HEIGHT + 1, val}, void();
  if constexpr (persistent) t= new Node{*t};
  id_t bits= (k >> ((HEIGHT + 1) - t->len));
  if (bits != t->bits) {
   uint8_t i= 64 - __builtin_clzll(bits ^ t->bits);
   bool flg= (t->bits >> (i - 1)) & 1;
   t->ch[flg]= new Node{*t}, t->ch[!flg]= new Node{k, HEIGHT + 1, val};
   t->len-= i, t->bits>>= i;
  } else if (t->len != HEIGHT + 1) {
   set_val(t->ch[(k >> (HEIGHT - t->len)) & 1], k, val);
  } else return t->val= val, void();
  if constexpr (monoid_v<M>) t->val= M::op(t->ch[0]->val, t->ch[1]->val);
 }
 T &at_val(np &t, const id_t &k) {
  if (!t) return t= new Node{k, HEIGHT + 1, def_val()}, t->val;
  if constexpr (persistent) t= new Node{*t};
  id_t bits= (k >> ((HEIGHT + 1) - t->len));
  if (bits != t->bits) {
   uint8_t i= 64 - __builtin_clzll(bits ^ t->bits);
   bool flg= (t->bits >> (i - 1)) & 1;
   t->ch[flg]= new Node{*t}, t->ch[!flg]= new Node{k, HEIGHT + 1, def_val()};
   t->len-= i, t->bits>>= i;
   return t->ch[!flg]->val;
  } else if (t->len != HEIGHT + 1) return at_val(t->ch[(k >> (HEIGHT - t->len)) & 1], k);
  return t->val;
 }
 bool is_null(np &t, const id_t &k) {
  if (!t || (k >> ((HEIGHT + 1) - t->len)) != t->bits) return true;
  if (t->len == HEIGHT + 1) return false;
  return is_null(t->ch[(k >> (HEIGHT - t->len)) & 1], k);
 }
 T get_val(np &t, const id_t &k) {
  if (!t || (k >> ((HEIGHT + 1) - t->len)) != t->bits) return def_val();
  if (t->len == HEIGHT + 1) return t->val;
  return get_val(t->ch[(k >> (HEIGHT - t->len)) & 1], k);
 }
 template <bool last> static inline T calc_op(np &t, const T &v) {
  if constexpr (last) return M::op((t ? t->val : def_val()), v);
  else return M::op(v, (t ? t->val : def_val()));
 }
 template <bool last> static inline bool is_in(const id_t &m, const id_t &k) {
  if constexpr (last) return k <= m;
  else return m <= k;
 }
 static inline np next(np &t, const uint8_t &h, const bool &f) {
  if (!t) return nullptr;
  uint8_t len= h + t->len - (HEIGHT + 1);
  if (!len) return t->ch[f];
  return (f == ((t->bits >> (len - 1)) & 1)) ? t : nullptr;
 }
 template <bool last, class C, std::size_t N> static id_t find(const id_t &k, std::array<id_t, 2> b, const id_t &bias, uint8_t h, const C &check, std::array<np, N> &ts, std::array<T, N> &sums) {
  static_assert(monoid_v<M>, "\"find\" is not available\n");
  static std::array<T, N> sums2;
  if (std::all_of(ts.begin(), ts.end(), [](np t) { return !t; })) return -1;
  if (!h) {
   for (std::size_t i= N; i--;) sums[i]= calc_op<last>(ts[i], sums[i]);
   return std::apply(check, sums) ? std::get<last>(b) : -1;
  } else if (is_in<last>(k, b[0])) {
   for (std::size_t i= N; i--;) sums2[i]= calc_op<last>(ts[i], sums[i]);
   if (!std::apply(check, sums2)) return sums= std::move(sums2), -1;
  }
  std::array<np, N> ss;
  id_t m= (b[0] + b[1]) >> 1;
  bool flg= (bias >> (h - 1)) & 1;
  if (!is_in<last>(m, k)) {
   for (std::size_t i= N; i--;) ss[i]= next(ts[i], h, flg);
   id_t ret= find<last>(k, {b[0], m}, bias, h - 1, check, ss, sums);
   if (ret >= 0) return ret;
  }
  for (std::size_t i= N; i--;) ss[i]= next(ts[i], h, !flg);
  return find<last>(k, {m, b[1]}, bias, h - 1, check, ss, sums);
 }
public:
 SegmentTree_Patricia(np t= nullptr): root(t) {}
 SegmentTree_Patricia(std::size_t n, T val): root(build(n, 0, 1LL << HEIGHT, val)) {}
 SegmentTree_Patricia(T *bg, T *ed): root(build(ed - bg, 0, 1LL << HEIGHT, bg)) {}
 SegmentTree_Patricia(const std::vector<T> &ar): SegmentTree_Patricia(ar.data(), ar.data() + ar.size()) {}
 void set(id_t k, T val) { set_val(root, k, val); }
 T get(id_t k) { return get_val(root, k); }
 bool is_null(id_t k) { return is_null(root, k); }
 T &at(id_t k) {
  static_assert(!monoid_v<M>, "\"at\" is not available\n");
  return at_val(root, k);
 }
 template <class L= M, std::enable_if_t<monoid_v<L>, std::nullptr_t> = nullptr> T operator[](id_t k) { return get(k); }
 template <class L= M, std::enable_if_t<!monoid_v<L>, std::nullptr_t> = nullptr> T &operator[](id_t k) { return at(k); }
 T prod(id_t a, id_t b, id_t bias= 0) {
  static_assert(monoid_v<M>, "\"prod\" is not available\n");
  return prod(root, a, b, bias);
 }
 // find i s.t.
 //  check(prod(k,i)) == False, check(prod(k,i+1)) == True
 // return -1 if not found
 template <class C> id_t find_first(id_t a, C check, id_t bias= 0) {
  std::array<T, 1> sum{def_val()};
  std::array<np, 1> t{root};
  return find<0>(a, {0, 1LL << HEIGHT}, bias, HEIGHT, check, t, sum);
 }
 template <std::size_t N, class C> static id_t find_first(id_t a, C check, std::array<SegmentTree_Patricia, N> segs, id_t bias= 0) {
  std::array<T, N> sums;
  sums.fill(def_val());
  std::array<np, N> ts;
  for (std::size_t i= 0; i < N; i++) ts[i]= segs[i].root;
  return find<0>(a, {0, 1LL << HEIGHT}, bias, HEIGHT, check, ts, sums);
 }
 // find i s.t.
 //  check(prod(i+1,k)) == False, check(prod(i,k)) == True
 // return -1 if not found
 template <class C> id_t find_last(id_t b, C check, id_t bias= 0) {
  std::array<T, 1> sum{def_val()};
  std::array<np, 1> t{root};
  return find<1>(b, {1LL << HEIGHT, 0}, ~bias, HEIGHT, check, t, sum);
 }
 template <std::size_t N, class C> static id_t find_last(id_t b, C check, std::array<SegmentTree_Patricia, N> segs, id_t bias= 0) {
  std::array<T, N> sums;
  sums.fill(def_val());
  std::array<np, N> ts;
  for (std::size_t i= 0; i < N; i++) ts[i]= segs[i].root;
  return find<1>(b, {1LL << HEIGHT, 0}, ~bias, HEIGHT, check, ts, sums);
 }
 std::vector<T> dump(id_t bg, id_t ed) {
  std::vector<T> ret(ed - bg);
  dump(root, bg, ed, {0, 1LL << HEIGHT}, ret.begin(), HEIGHT);
  return ret;
 }
 static std::string which_available() {
  std::string ret= "";
  if constexpr (monoid_v<M>) ret+= "\"prod\" \"find\"";
  else ret+= "\"at\" ";
  return ret;
 }
};
#line 4 "src/Internal/ListRange.hpp"
#include <iterator>
#line 6 "src/Internal/ListRange.hpp"
#define _LR(name, IT, CT) \
 template <class T> struct name { \
  using Iterator= typename std::vector<T>::IT; \
  Iterator bg, ed; \
  Iterator begin() const { return bg; } \
  Iterator end() const { return ed; } \
  size_t size() const { return std::distance(bg, ed); } \
  CT &operator[](int i) const { return bg[i]; } \
 }
_LR(ListRange, iterator, T);
_LR(ConstListRange, const_iterator, const T);
#undef _LR
template <class T> struct CSRArray {
 std::vector<T> dat;
 std::vector<int> p;
 size_t size() const { return p.size() - 1; }
 ListRange<T> operator[](int i) { return {dat.begin() + p[i], dat.begin() + p[i + 1]}; }
 ConstListRange<T> operator[](int i) const { return {dat.cbegin() + p[i], dat.cbegin() + p[i + 1]}; }
};
template <template <class> class F, class T> std::enable_if_t<std::disjunction_v<std::is_same<F<T>, ListRange<T>>, std::is_same<F<T>, ConstListRange<T>>, std::is_same<F<T>, CSRArray<T>>>, std::ostream &> operator<<(std::ostream &os, const F<T> &r) {
 os << '[';
 for (int _= 0, __= r.size(); _ < __; ++_) os << (_ ? ", " : "") << r[_];
 return os << ']';
}
#line 3 "src/Graph/Graph.hpp"
struct Edge: std::pair<int, int> {
 using std::pair<int, int>::pair;
 Edge &operator--() { return --first, --second, *this; }
 int to(int v) const { return first ^ second ^ v; }
 friend std::istream &operator>>(std::istream &is, Edge &e) { return is >> e.first >> e.second, is; }
};
struct Graph: std::vector<Edge> {
 size_t n;
 Graph(size_t n= 0, size_t m= 0): vector(m), n(n) {}
 size_t vertex_size() const { return n; }
 size_t edge_size() const { return size(); }
 size_t add_vertex() { return n++; }
 size_t add_edge(int s, int d) { return emplace_back(s, d), size() - 1; }
 size_t add_edge(Edge e) { return emplace_back(e), size() - 1; }
#define _ADJ_FOR(a, b) \
 for (auto [u, v]: *this) a; \
 for (size_t i= 0; i < n; ++i) p[i + 1]+= p[i]; \
 for (int i= size(); i--;) { \
  auto [u, v]= (*this)[i]; \
  b; \
 }
#define _ADJ(a, b) \
 vector<int> p(n + 1), c(size() << !dir); \
 if (!dir) { \
  _ADJ_FOR((++p[u], ++p[v]), (c[--p[u]]= a, c[--p[v]]= b)) \
 } else if (dir > 0) { \
  _ADJ_FOR(++p[u], c[--p[u]]= a) \
 } else { \
  _ADJ_FOR(++p[v], c[--p[v]]= b) \
 } \
 return {c, p}
 CSRArray<int> adjacency_vertex(int dir) const { _ADJ(v, u); }
 CSRArray<int> adjacency_edge(int dir) const { _ADJ(i, i); }
#undef _ADJ
#undef _ADJ_FOR
};
#line 3 "src/Graph/HeavyLightDecomposition.hpp"
#include <cassert>
#line 5 "src/Graph/HeavyLightDecomposition.hpp"
class HeavyLightDecomposition {
 std::vector<int> P, PP, D, I, L, R;
public:
 HeavyLightDecomposition()= default;
 HeavyLightDecomposition(const Graph &g, int root= 0): HeavyLightDecomposition(g.adjacency_vertex(0), root) {}
 HeavyLightDecomposition(const CSRArray<int> &adj, int root= 0) {
  const int n= adj.size();
  P.assign(n, -2), PP.resize(n), D.resize(n), I.resize(n), L.resize(n), R.resize(n);
  auto f= [&, i= 0, v= 0, t= 0](int r) mutable {
   for (P[r]= -1, I[t++]= r; i < t; ++i)
    for (int u: adj[v= I[i]])
     if (P[v] != u) P[I[t++]= u]= v;
  };
  f(root);
  for (int r= 0; r < n; ++r)
   if (P[r] == -2) f(r);
  std::vector<int> Z(n, 1), nx(n, -1);
  for (int i= n, v; i--;) {
   if (P[v= I[i]] == -1) continue;
   if (Z[P[v]]+= Z[v]; nx[P[v]] == -1) nx[P[v]]= v;
   if (Z[nx[P[v]]] < Z[v]) nx[P[v]]= v;
  }
  for (int v= n; v--;) PP[v]= v;
  for (int v: I)
   if (nx[v] != -1) PP[nx[v]]= v;
  for (int v: I)
   if (P[v] != -1) PP[v]= PP[PP[v]], D[v]= D[P[v]] + 1;
  for (int i= n; i--;) L[I[i]]= i;
  for (int v: I) {
   int ir= R[v]= L[v] + Z[v];
   for (int u: adj[v])
    if (u != P[v] && u != nx[v]) L[u]= (ir-= Z[u]);
   if (nx[v] != -1) L[nx[v]]= L[v] + 1;
  }
  for (int i= n; i--;) I[L[i]]= i;
 }
 int to_seq(int v) const { return L[v]; }
 int to_vertex(int i) const { return I[i]; }
 size_t size() const { return P.size(); }
 int parent(int v) const { return P[v]; }
 int head(int v) const { return PP[v]; }
 int root(int v) const {
  for (v= PP[v];; v= PP[P[v]])
   if (P[v] == -1) return v;
 }
 bool connected(int u, int v) const { return root(u) == root(v); }
 // u is in v
 bool in_subtree(int u, int v) const { return L[v] <= L[u] && L[u] < R[v]; }
 int subtree_size(int v) const { return R[v] - L[v]; }
 int lca(int u, int v) const {
  for (;; v= P[PP[v]]) {
   if (L[u] > L[v]) std::swap(u, v);
   if (PP[u] == PP[v]) return u;
  }
 }
 int la(int v, int k) const {
  assert(k <= D[v]);
  for (int u;; k-= L[v] - L[u] + 1, v= P[u])
   if (L[v] - k >= L[u= PP[v]]) return I[L[v] - k];
 }
 int jump(int u, int v, int k) const {
  if (!k) return u;
  if (u == v) return -1;
  if (k == 1) return in_subtree(v, u) ? la(v, D[v] - D[u] - 1) : P[u];
  int w= lca(u, v), d_uw= D[u] - D[w], d_vw= D[v] - D[w];
  return k > d_uw + d_vw ? -1 : k <= d_uw ? la(u, k) : la(v, d_uw + d_vw - k);
 }
 int depth(int v) const { return D[v]; }
 int dist(int u, int v) const { return D[u] + D[v] - D[lca(u, v)] * 2; }
 // half-open interval [l,r)
 std::pair<int, int> subtree(int v) const { return {L[v], R[v]}; }
 // sequence of closed intervals [l,r]
 std::vector<std::pair<int, int>> path(int u, int v, bool edge= 0) const {
  std::vector<std::pair<int, int>> up, down;
  while (PP[u] != PP[v]) {
   if (L[u] < L[v]) down.emplace_back(L[PP[v]], L[v]), v= P[PP[v]];
   else up.emplace_back(L[u], L[PP[u]]), u= P[PP[u]];
  }
  if (L[u] < L[v]) down.emplace_back(L[u] + edge, L[v]);
  else if (L[v] + edge <= L[u]) up.emplace_back(L[u], L[v] + edge);
  return up.insert(up.end(), down.rbegin(), down.rend()), up;
 }
};
#line 12 "test/atcoder/abc133_f.Patricia.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 Graph g(N, N - 1);
 vector<int> c(N - 1), d(N - 1);
 for (int i= 0; i < N - 1; ++i) cin >> g[i] >> c[i] >> d[i], --g[i];
 HeavyLightDecomposition hld(g, 0);
 using PerArr= SegmentTree_Patricia<int, true, 17>;
 vector<PerArr> Arr1(N), Arr2(N);
 vector<int> dep(N);
 auto adj= g.adjacency_edge(0);
 for (int i= 0; i < N; ++i) {
  int v= hld.to_vertex(i), p= hld.parent(v);
  for (int e: adj[v]) {
   int u= g[e].to(v);
   if (u == p) continue;
   Arr1[u]= Arr1[v], Arr2[u]= Arr2[v];
   Arr1[u][c[e]]+= 1, Arr2[u][c[e]]+= d[e];
   dep[u]= dep[v] + d[e];
  }
 }
 for (int i= 0; i < Q; i++) {
  int x, y, u, v;
  cin >> x >> y >> u >> v;
  int lca= hld.lca(--u, --v);
  cout << dep[u] + dep[v] - 2 * dep[lca] + y * (Arr1[u].get(x) + Arr1[v].get(x) - 2 * Arr1[lca].get(x)) - (Arr2[u].get(x) + Arr2[v].get(x) - 2 * Arr2[lca].get(x)) << '\n';
 }
 return 0;
}
Back to top page