//#define NDEBUG #include #include #include #include #include namespace n91 { using i8 = std::int_fast8_t; using i32 = std::int_fast32_t; using i64 = std::int_fast64_t; using u8 = std::uint_fast8_t; using u32 = std::uint_fast32_t; using u64 = std::uint_fast64_t; using isize = std::ptrdiff_t; using usize = std::size_t; constexpr usize operator"" _z(unsigned long long x) noexcept { return static_cast(x); } template class integral_iterator { public: using difference_type = T; using value_type = T; using pointer = const value_type*; using reference = value_type; using iterator_category = std::random_access_iterator_tag; private: using self_type = integral_iterator; value_type i; public: constexpr integral_iterator() noexcept : i() {} explicit constexpr integral_iterator(const value_type i) noexcept : i(i) {} constexpr self_type operator++(int) noexcept { return self_type(i++); } constexpr self_type operator--(int) noexcept { return self_type(i--); } constexpr self_type operator[](const difference_type rhs) const noexcept { return self_type(i + rhs); } constexpr self_type& operator++() noexcept { ++i; return *this; } constexpr self_type& operator--() noexcept { --i; return *this; } constexpr reference operator*() const noexcept { return i; } constexpr self_type operator+(const difference_type rhs) const noexcept { return self_type(i + rhs); } constexpr self_type operator-(const difference_type rhs) const noexcept { return self_type(i - rhs); } constexpr difference_type operator-(const self_type rhs) const noexcept { return i - rhs.i; } constexpr bool operator<(const self_type rhs) const noexcept { return i < rhs.i; } constexpr bool operator<=(const self_type rhs) const noexcept { return i <= rhs.i; } constexpr bool operator>(const self_type rhs) const noexcept { return i > rhs.i; } constexpr bool operator>=(const self_type rhs) const noexcept { return i >= rhs.i; } constexpr bool operator==(const self_type rhs) const noexcept { return i == rhs.i; } constexpr bool operator!=(const self_type rhs) const noexcept { return i != rhs.i; } constexpr self_type& operator+=(const difference_type rhs) noexcept { i += rhs; return *this; } constexpr self_type& operator-=(const difference_type rhs) noexcept { i -= rhs; return *this; } }; template constexpr integral_iterator make_int_itr(const T i) noexcept { return integral_iterator(i); } class rep { const usize f, l; public: constexpr rep(const usize f, const usize l) noexcept : f(f), l(l) {} constexpr auto begin() const noexcept { return make_int_itr(f); } constexpr auto end() const noexcept { return make_int_itr(l); } }; class revrep { const usize f, l; public: revrep(const usize f, const usize l) noexcept : f(l), l(f) {} auto begin() const noexcept { return std::make_reverse_iterator(make_int_itr(f)); } auto end() const noexcept { return std::make_reverse_iterator(make_int_itr(l)); } }; template auto md_vec(const usize n, const T& value) { return std::vector(n, value); } template auto md_vec(const usize n, Args... args) { return std::vector(n, md_vec(args...)); } template constexpr T difference(const T& a, const T& b) { return a < b ? b - a : a - b; } template T scan() { T ret; std::cin >> ret; return ret; } } // namespace n91 #include #include #include class rooted_trees { private: class node_type; using container_type = ::std::vector; public: using size_type = typename container_type::size_type; private: class node_type { using pointer = node_type *; pointer left, right, parent; bool reversed; public: node_type() : left(nullptr), right(nullptr), parent(nullptr), reversed(false) {} void reverse() { reversed = !reversed; } void cut_left() { if (left) { left->parent = nullptr; left = nullptr; } } void push() { if (reversed) { reversed = false; ::std::swap(left, right); if (left) left->reverse(); if (right) right->reverse(); } } void set_left_of(const pointer ptr) { ptr->left = this; parent = ptr; } void set_right_of(const pointer ptr) { ptr->right = this; parent = ptr; } void rotate_as_left(const pointer ptr) { if (right) right->set_left_of(ptr); else ptr->left = nullptr; ptr->set_right_of(this); } void rotate_as_right(const pointer ptr) { if (left) left->set_right_of(ptr); else ptr->right = nullptr; ptr->set_left_of(this); } void splay() { for (pointer x, y = this;;) { if (x = parent) { if (x->left == y) { if (y = x->parent) { if (y->left == x) { parent = y->parent; x->rotate_as_left(y); rotate_as_left(x); } else if (y->right == x) { parent = y->parent; rotate_as_left(x); rotate_as_right(y); } else { parent = y; rotate_as_left(x); return; } } else { parent = nullptr; rotate_as_left(x); return; } } else if (x->right == y) { if (y = x->parent) { if (y->left == x) { parent = y->parent; rotate_as_right(x); rotate_as_left(y); } else if (y->right == x) { parent = y->parent; x->rotate_as_right(y); rotate_as_right(x); } else { parent = y; rotate_as_right(x); return; } } else { parent = nullptr; rotate_as_right(x); return; } } else { return; } } else { return; } } } static void propagate(pointer ptr) { pointer prev = nullptr; while (ptr) { ::std::swap(ptr->parent, prev); ::std::swap(ptr, prev); } while (prev) { prev->push(); ::std::swap(prev->parent, ptr); ::std::swap(prev, ptr); } } pointer expose() { propagate(this); pointer x = this, prev = nullptr; while (x) { x->splay(); x->right = prev; prev = x; x = x->parent; } splay(); return prev; } bool exposed_just_before() const { return !static_cast(parent); } bool is_root() const { return !static_cast(left); } pointer splay_prev() { node_type temp; pointer subtree = &temp; pointer cur = left, cur_r; left = nullptr; while (cur->push(), cur_r = cur->right) { cur_r->push(); if (cur_r->right) { cur_r->rotate_as_right(cur); cur_r->set_right_of(subtree); subtree = cur_r; cur = cur_r->right; } else { cur->set_right_of(subtree); subtree = cur; cur = cur_r; break; } } cur->parent = nullptr; if (cur->left) cur->left->set_right_of(subtree); if (temp.right) temp.right->set_left_of(cur); else cur->left = nullptr; set_right_of(cur); return cur; } }; using pointer = node_type *; container_type nodes; pointer get_ptr(const size_type v) { return &nodes[v]; } size_type get_index(const pointer p) { return static_cast(p - nodes.data()); } public: explicit rooted_trees(const size_type size) : nodes(size) {} bool empty() const { return nodes.empty(); } size_type size() const { return nodes.size(); } bool is_root(const size_type v) { assert(v < size()); nodes[v].expose(); return nodes[v].is_root(); } bool is_connected(const size_type v, const size_type w) { assert(v < size()); assert(w < size()); if (v == w) return true; nodes[v].expose(); nodes[w].expose(); return !nodes[v].exposed_just_before(); } size_type lca(const size_type v, const size_type w) { assert(v < size()); assert(w < size()); if (v == w) return v; nodes[v].expose(); pointer ptr = nodes[w].expose(); if (nodes[v].exposed_just_before()) return size(); if (!static_cast(ptr)) return w; return get_index(ptr); } size_type parent(const size_type v) { assert(v < size()); nodes[v].expose(); if (nodes[v].is_root()) return size(); else return get_index(nodes[v].splay_prev()); } void reroot(const size_type v) { assert(v < size()); nodes[v].expose(); nodes[v].reverse(); } void set_parent(const size_type v, const size_type p) { assert(v < size()); assert(p < size()); cut(v); assert(!is_connected(v, p)); nodes[p].expose(); nodes[p].set_left_of(get_ptr(v)); } void cut(const size_type v) { assert(v < size()); nodes[v].expose(); nodes[v].cut_left(); } ::std::vector<::std::pair> all_edges() { ::std::vector<::std::pair> ret; for (size_type i = static_cast(0); i < size(); ++i) { const size_type p = parent(i); if (p != size()) ret.emplace_back(p, i); } return ::std::move(ret); } }; #include #include #include #include #include template class lazy_st_trees { public: using value_structure = ValueMonoid; using value_type = typename value_structure::value_type; using operator_structure = OperatorMonoid; using operator_type = typename operator_structure::value_type; using modifier = Modifier; private: class node_type { public: node_type* left, * right, * parent; typename lazy_st_trees::value_type value, sum; typename lazy_st_trees::operator_type lazy; bool reversed; // reverse->lazy node_type(node_type* const p) : left(p), right(p), parent(p), value(value_structure::identity()), sum(value_structure::identity()), lazy(operator_structure::identity()), reversed(0) {} }; using container_type = ::std::vector; public: using size_type = typename container_type::size_type; private: using pointer = node_type *; using const_pointer = const node_type*; static void reverse(const pointer ptr) { ptr->lazy = operator_structure::reverse(::std::move(ptr->lazy)); ptr->reversed ^= 1; } static void push(const pointer ptr) { if (ptr->reversed) { ptr->reversed = 0; ptr->value = value_structure::reverse(::std::move(ptr->value)); ::std::swap(ptr->left, ptr->right); reverse(ptr->left); reverse(ptr->right); } ptr->left->lazy = operator_structure::operation(ptr->left->lazy, ptr->lazy); ptr->right->lazy = operator_structure::operation(ptr->right->lazy, ptr->lazy); ptr->value = modifier::operation(ptr->value, ptr->lazy); ptr->lazy = operator_structure::identity(); } void propagate(pointer ptr) { pointer prev = nullptr; while (ptr != nil()) { ::std::swap(ptr->parent, prev); ::std::swap(ptr, prev); } while (prev) { push(prev); ::std::swap(prev->parent, ptr); ::std::swap(prev, ptr); } nil()->sum = value_structure::identity(); nil()->lazy = operator_structure::identity(); nil()->reversed = 0; } static value_type reflect(const const_pointer ptr) { return modifier::operation( ptr->reversed ? value_structure::reverse(ptr->sum) : ptr->sum, ptr->lazy); } static void calc(const pointer ptr) { ptr->sum = value_structure::operation( value_structure::operation(reflect(ptr->left), ptr->value), reflect(ptr->right)); } static void rotate_l(const pointer ptr, const pointer ch) { ptr->right = ch->left; ch->left->parent = ptr; calc(ptr); ch->left = ptr; ptr->parent = ch; } static void rotate_r(const pointer ptr, const pointer ch) { ptr->left = ch->right; ch->right->parent = ptr; calc(ptr); ch->right = ptr; ptr->parent = ch; } static void splay(const pointer ptr) { for (pointer x, y = ptr;;) { x = ptr->parent; if (x->left == y) { y = x->parent; ptr->parent = y->parent; if (y->left == x) rotate_r(y, x), rotate_r(x, ptr); else if (y->right == x) rotate_l(y, ptr), rotate_r(x, ptr); else return ptr->parent = y, rotate_r(x, ptr); } else if (x->right == y) { y = x->parent; ptr->parent = y->parent; if (y->right == x) rotate_l(y, x), rotate_l(x, ptr); else if (y->left == x) rotate_r(y, ptr), rotate_l(x, ptr); else return ptr->parent = y, rotate_l(x, ptr); } else { return; } } } void expose(const pointer ptr) { propagate(ptr); pointer x = ptr, prev = nil(); while (x != nil()) { splay(x); x->right = prev; calc(x); prev = x; x = x->parent; } splay(ptr); calc(ptr); } void reroot(const pointer ptr) { expose(ptr); reverse(ptr); } container_type nodes; pointer get_ptr(const size_type v) { return nodes.data() + v; } pointer nil() { return &nodes.back(); } public: lazy_st_trees() : nodes() {} explicit lazy_st_trees(const size_type size) : nodes() { nodes.reserve(size + 1); nodes.resize(size + 1, node_type(nodes.data() + size)); } bool empty() const { return size() == 0; } size_type size() const { return nodes.size() - 1; } bool connected(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); expose(get_ptr(v)); expose(get_ptr(u)); return nodes[v].parent != nil() || v == u; } value_type fold_path(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); return nodes[u].sum; } void link(const size_type parent, const size_type child) { assert(parent < size()); assert(child < size()); assert(!connected(parent, child)); reroot(get_ptr(child)); nodes[child].parent = get_ptr(parent); } void cut(const size_type v) { assert(v < size()); expose(get_ptr(v)); nodes[v].left->parent = nil(); nodes[v].left = nil(); nodes[v].sum = nodes[v].value; } void update_path(const size_type v, const size_type u, const operator_type& value) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); nodes[u].lazy = value; } template void update_vertex(const size_type v, const F& f) { assert(v < size()); expose(get_ptr(v)); nodes[v].value = f(::std::move(nodes[v].value)); calc(get_ptr(v)); } }; #include class trivial_group { public: using value_type = std::tuple<>; static constexpr value_type operation(const value_type, const value_type) noexcept { return value_type(); } static constexpr value_type identity() noexcept { return value_type(); } static constexpr value_type inverse(const value_type) noexcept { return value_type(); } static constexpr value_type reverse(const value_type) noexcept { return value_type(); } }; template class trivial_action { public: static constexpr typename T::value_type operation(const typename T::value_type& lhs, const typename trivial_group::value_type) noexcept { return lhs; } }; template class plus_monoid { public: using value_type = T; static value_type operation(const value_type& x, const value_type& y) { return x + y; } static value_type identity() { return value_type(0); } static value_type reverse(const value_type& x) { return x; } }; #include #include #include namespace n91 { void main_() { const usize n = scan(); lazy_st_trees, trivial_group, trivial_action>> lst(n * 2_z); auto g = md_vec(n, 0_z, usize()); for (const auto i : rep(0_z, n - 1_z)) { const usize u = scan(); const usize v = scan(); const u64 w = scan(); g[u].push_back(v); g[v].push_back(u); lst.link(u, n+i); lst.link(n+i, v); lst.update_vertex(n+i, [&](auto) { return w; }); } std::vector et(n); { usize cnt = 0_z; const auto dfs = [&](const auto& dfs, const usize v, const usize p) -> void { et[v] = cnt++; for (const auto e : g[v]) { if (e != p) { dfs(dfs, e, v); } } }; dfs(dfs, 0_z, n); } const usize q = scan(); for (const auto i : rep(0_z, q)) { const usize k = 3_z; std::vector x(k); for (auto& e : x) { std::cin >> e; } std::sort(x.begin(), x.end(), [&](usize l, usize r) { return et[l] < et[r]; }); u64 ans = static_cast(0); for (const auto i : rep(0_z, k)) { ans += lst.fold_path(x[i], x[(i + 1_z) % k]); } std::cout << ans / static_cast(2) << std::endl; } } } // namespace n91 int main() { n91::main_(); return 0; }