This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc133/tasks/abc133_f
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 128
// 永続配列(at) の verify
#include <iostream>
#include <vector>
#include "src/DataStructure/SegmentTree_Dynamic.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_Dynamic<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.DynSeg.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc133/tasks/abc133_f
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 128
// 永続配列(at) の verify
#include <iostream>
#include <vector>
#line 2 "src/DataStructure/SegmentTree_Dynamic.hpp"
#include <array>
#line 4 "src/DataStructure/SegmentTree_Dynamic.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_Dynamic.hpp"
template <typename M, bool persistent= false, uint8_t HEIGHT= 31> class SegmentTree_Dynamic {
HAS_MEMBER(op);
HAS_MEMBER(ti);
HAS_MEMBER(mp);
HAS_MEMBER(cp);
HAS_TYPE(T);
HAS_TYPE(E);
NULLPTR_OR(E);
template <class L> static constexpr bool monoid_v= std::conjunction_v<has_T<L>, has_op<L>, has_ti<L>>;
template <class L> static constexpr bool dual_v= std::conjunction_v<has_T<L>, has_E<L>, has_mp<L>, has_cp<L>>;
using id_t= long long;
template <class T, class tDerived> struct Node_B {
T val;
tDerived *ch[2]= {nullptr, nullptr};
};
template <bool mo, bool du, typename tEnable= void> struct Node_D: Node_B<M, Node_D<mo, du, tEnable>> {};
template <bool mo, bool du> struct Node_D<mo, du, typename std::enable_if_t<mo && !du>>: Node_B<typename M::T, Node_D<mo, du>> {};
template <bool mo, bool du> struct Node_D<mo, du, typename std::enable_if_t<du>>: Node_B<typename M::T, Node_D<mo, du>> {
typename M::E lazy;
bool lazy_flg= false;
};
using Node= Node_D<monoid_v<M>, dual_v<M>>;
using T= decltype(Node::val);
using E= nullptr_or_E_t<M>;
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(id_t n, id_t l, id_t r, const S &bg) {
if (n <= l) return nullptr;
if (r - l == 1) {
if constexpr (std::is_same_v<S, T>) return new Node{bg};
else return new Node{*(bg + l)};
}
id_t m= (r + l) / 2;
np t= new Node{def_val(), {build(n, l, m, bg), build(n, m, r, bg)}};
if constexpr (monoid_v<M>) update(t);
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) {
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) {
if constexpr (dual_v<M>) push(t, b[1] - b[0]);
auto m= (b[0] + b[1]) >> 1;
dump(t ? t->ch[0] : nullptr, l, r, {b[0], m}, itr);
dump(t ? t->ch[1] : nullptr, l, r, {m, b[1]}, itr);
} else *(itr + b[0])= t->val;
}
static inline void update(np &t) {
t->val= def_val();
if (t->ch[0]) t->val= M::op(t->ch[0]->val, t->val);
if (t->ch[1]) t->val= M::op(t->val, t->ch[1]->val);
}
static inline void map(T &v, E x, int sz) {
if constexpr (std::is_invocable_r_v<void, decltype(M::mp), T &, E, int>) M::mp(v, x, sz);
else M::mp(v, x);
}
static inline T &reflect(np &t) {
if constexpr (dual_v<M> && !monoid_v<M>)
if (t->lazy_flg) map(t->val, t->lazy, 1), t->lazy_flg= false;
return t->val;
}
static inline void propagate(np &t, const E &x, const id_t &sz) {
t->lazy_flg ? (M::cp(t->lazy, x), x) : t->lazy= x;
t->lazy_flg= true;
if constexpr (monoid_v<M>) map(t->val, x, sz);
}
static inline void cp_node(np &t) {
if (!t) t= new Node{def_val()};
else if constexpr (persistent) t= new Node(*t);
}
static inline void push(np &t, const id_t &sz) {
if (!t->lazy_flg) return;
cp_node(t->ch[0]), cp_node(t->ch[1]), t->lazy_flg= false;
propagate(t->ch[0], t->lazy, sz / 2), propagate(t->ch[1], t->lazy, sz / 2);
}
T prod(np &t, const id_t &l, const id_t &r, std::array<id_t, 2> b, const id_t &bias) {
if (!t || r <= b[0] || b[1] <= l) return def_val();
if (l <= b[0] && b[1] <= r) return t->val;
if constexpr (dual_v<M>) push(t, b[1] - b[0]);
id_t m= (b[0] + b[1]) >> 1;
bool flg= (bias >> (__builtin_ctzll(b[1] - b[0]) - 1)) & 1;
return M::op(prod(t->ch[flg], l, r, {b[0], m}, bias), prod(t->ch[!flg], l, r, {m, b[1]}, bias));
}
void apply(np &t, const id_t &l, const id_t &r, std::array<id_t, 2> b, const E &x) {
if (r <= b[0] || b[1] <= l) return;
id_t m= (b[0] + b[1]) >> 1;
if (cp_node(t); l <= b[0] && b[1] <= r) return propagate(t, x, b[1] - b[0]);
push(t, b[1] - b[0]);
apply(t->ch[0], l, r, {b[0], m}, x), apply(t->ch[1], l, r, {m, b[1]}, x);
if constexpr (monoid_v<M>) update(t);
}
void set_val(np &t, const id_t &k, const T &val, uint8_t h) {
if (cp_node(t); !h) return reflect(t)= val, void();
if constexpr (dual_v<M>) push(t, 1LL << h);
set_val(t->ch[(k >> (h - 1)) & 1], k, val, h - 1);
if constexpr (monoid_v<M>) update(t);
}
T &at_val(np &t, const id_t &k, uint8_t h) {
if (cp_node(t); !h) return reflect(t);
if constexpr (dual_v<M>) push(t, 1LL << h);
return at_val(t->ch[(k >> (h - 1)) & 1], k, h - 1);
}
bool is_null(np &t, const id_t &k, uint8_t h) {
if (!t) return true;
if (!h) return false;
if constexpr (dual_v<M>) push(t, 1LL << h);
return is_null(t->ch[(k >> (h - 1)) & 1], k, h - 1);
}
T get_val(np &t, const id_t &k, uint8_t h) {
if (!t) return def_val();
if (!h) return reflect(t);
if constexpr (dual_v<M>) push(t, 1LL << h);
return get_val(t->ch[(k >> (h - 1)) & 1], k, h - 1);
}
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;
}
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;
}
if constexpr (dual_v<M>)
for (std::size_t i= N; i--;) push(ts[i], b[1] - b[0]);
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]= ts[i] ? ts[i]->ch[flg] : nullptr;
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]= ts[i] ? ts[i]->ch[!flg] : nullptr;
return find<last>(k, {m, b[1]}, bias, h - 1, check, ss, sums);
}
public:
SegmentTree_Dynamic(np t= nullptr): root(t) {}
SegmentTree_Dynamic(std::size_t n, T val): root(build(n, 0, 1LL << HEIGHT, val)) {}
SegmentTree_Dynamic(const T *bg, const T *ed): root(build(ed - bg, 0, 1LL << HEIGHT, bg)) {}
SegmentTree_Dynamic(const std::vector<T> &ar): SegmentTree_Dynamic(ar.data(), ar.data() + ar.size()) {}
void set(id_t k, T val) { set_val(root, k, val, HEIGHT); }
T get(id_t k) { return get_val(root, k, HEIGHT); }
bool is_null(id_t k) { return is_null(root, k, HEIGHT); }
T &at(id_t k) {
static_assert(!monoid_v<M>, "\"at\" is not available\n");
return at_val(root, k, HEIGHT);
}
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, {0, 1LL << HEIGHT}, bias);
}
// find i s.t.
// check(prod(a,i)) == False, check(prod(a,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_Dynamic, 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,b)) == False, check(prod(i,b)) == 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_Dynamic, 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);
}
void apply(id_t a, id_t b, E x) {
static_assert(dual_v<M>, "\"apply\" is not available\n");
apply(root, a, b, {0, 1LL << HEIGHT}, x);
}
std::vector<T> dump(id_t bg, id_t ed) {
std::vector<T> ret(ed - bg);
return dump(root, bg, ed, {0, 1LL << HEIGHT}, ret.begin()), ret;
}
static std::string which_available() {
std::string ret= "";
if constexpr (monoid_v<M>) ret+= "\"prod\" \"find\" ";
else ret+= "\"at\" ";
if constexpr (dual_v<M>) ret+= "\"apply\" ";
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.DynSeg.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_Dynamic<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;
}