#include using namespace std; #pragma region template using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template using V = vector; template using VV = V>; #ifdef LOCAL struct PrettyOS { ostream& os; bool first; template auto operator<<(T&& x) { if (!first) os << ", "; first = false; os << x; return *this; } }; template void dbg0(T&&... t) { (PrettyOS{cerr, true} << ... << t); } #define dbg(...) \ do { \ cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \ dbg0(__VA_ARGS__); \ cerr << endl; \ } while (false); #else #define dbg(...) #endif template ostream& operator<<(ostream& os, const pair& p) { return os << "P(" << p.first << ", " << p.second << ")"; } template ostream& operator<<(ostream& os, const V& v) { os << "["; for (auto d : v) os << d << ", "; return os << "]"; } struct Scanner { FILE* fp = nullptr; char line[1 << 15]; size_t st = 0, ed = 0; void reread() { memmove(line, line + st, ed - st); ed -= st; st = 0; ed += fread(line + ed, 1, (1 << 15) - ed, fp); } bool succ() { while (true) { if (st == ed) { reread(); if (st == ed) return false; } while (st != ed && isspace(line[st])) st++; if (st != ed) break; } if (ed - st <= 50) reread(); return true; } template ::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; while (true) { succ(); size_t sz = 1; while (st + sz < ed && !isspace(line[st + sz])) sz++; ref.append(line + st, sz); st += sz; if (st != ed) break; } return true; } template ::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; bool neg = false; if (line[st] == '-') { neg = true; st++; } ref = T(0); while (isdigit(line[st])) { ref = 10 * ref + (line[st++] - '0'); } if (neg) ref = -ref; return true; } template bool read_single(V& ref) { for (auto& d: ref) { if (!read_single(d)) return false; } return true; } void read() {} template void read(H& h, T&... t) { bool f = read_single(h); assert(f); read(t...); } Scanner(FILE* _fp) : fp(_fp) {} }; struct Printer { public: template void write() {} template void write(const H& h, const T&... t) { if (F) write_single(' '); write_single(h); write(t...); } template void writeln(const T&... t) { write(t...); write_single('\n'); } Printer(FILE* _fp) : fp(_fp) {} ~Printer() { flush(); } private: static constexpr size_t SIZE = 1 << 15; FILE* fp; char line[SIZE], small[50]; size_t pos = 0; void flush() { fwrite(line, 1, pos, fp); pos = 0; } void write_single(const char& val) { if (pos == SIZE) flush(); line[pos++] = val; } template ::value, int> = 0> void write_single(const T& val) { for (char c : val) write_single(c); } template ::value, int> = 0> void write_single(T val) { if (pos > (1 << 15) - 50) flush(); if (val == 0) { write_single('0'); return; } if (val < 0) { write_single('-'); val = -val; // todo min } size_t len = 0; while (val) { small[len++] = char('0' + (val % 10)); val /= 10; } reverse(small, small + len); memcpy(line + pos, small, len); pos += len; } template void write_single(const V& val) { auto n = val.size(); for (size_t i = 0; i < n; i++) { if (i) write_single(' '); write_single(val[i]); } } }; #pragma endregion #pragma once #include #include #include #include #include #include #include struct Random { private: // Use xoshiro256** // Refereces: http://xoshiro.di.unimi.it/xoshiro256starstar.c static uint64_t rotl(const uint64_t x, int k) { return (x << k) | (x >> (64 - k)); } std::array s; uint64_t next() { const uint64_t result_starstar = rotl(s[1] * 5, 7) * 9; const uint64_t t = s[1] << 17; s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3]; s[2] ^= t; s[3] = rotl(s[3], 45); return result_starstar; } // random choice from [0, upper] uint64_t next(uint64_t upper) { if (!(upper & (upper + 1))) { // b = 00..0011..11 return next() & upper; } int lg = 63 - __builtin_clzll(upper); uint64_t mask = (lg == 63) ? ~0ULL : (1ULL << (lg + 1)) - 1; while (true) { uint64_t r = next() & mask; if (r <= upper) return r; } } public: Random(uint64_t seed = 0) { // Use splitmix64 // Reference: http://xoshiro.di.unimi.it/splitmix64.c for (int i = 0; i < 4; i++) { uint64_t z = (seed += 0x9e3779b97f4a7c15); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; z = (z ^ (z >> 27)) * 0x94d049bb133111eb; s[i] = z ^ (z >> 31); } } // random choice from [lower, upper] template T uniform(T lower, T upper) { assert(lower <= upper); return T(lower + next(uint64_t(upper - lower))); } bool uniform_bool() { return uniform(0, 1) == 1; } double uniform01() { uint64_t v = next(1ULL << 63); return double(v) / (1ULL << 63); } // generate random lower string that length = n std::string lower_string(size_t n) { std::string res = ""; for (size_t i = 0; i < n; i++) { res += uniform('a', 'z'); } return res; } // random shuffle template void shuffle(Iter first, Iter last) { // Reference and edit: // cpprefjp - C++日本語リファレンス // (https://cpprefjp.github.io/reference/algorithm/shuffle.html) int len = 1; for (auto it = first + 1; it != last; it++) { len++; int j = uniform(0, len - 1); if (j != len - 1) iter_swap(it, first + j); } } // generate random permutation that length = n template std::vector perm(size_t n) { std::vector idx(n); std::iota(idx.begin(), idx.end(), T(0)); shuffle(idx.begin(), idx.end()); return idx; } template std::vector choice(size_t n, T lower, T upper) { assert(n <= upper - lower + 1); std::set res; while (res.size() < n) res.insert(uniform(lower, upper)); return {res.begin(), res.end()}; } } global_gen; template struct LCNode { using NP = LCNode*; using D = typename N::D; NP p = nullptr, l = nullptr, r = nullptr; int sz = 1; bool rev = false; D v = N::e_d(), sm = N::e_d(); void single_add(D x) { v = N::op_dd(v, x); update(); } void init_node(D _v) { v = _v; sm = _v; } void update() { sz = 1; if (l) sz += l->sz; if (r) sz += r->sz; sm = l ? N::op_dd(l->sm, v) : v; if (r) sm = N::op_dd(sm, r->sm); } void push() { if (rev) { if (l) l->revdata(); if (r) r->revdata(); rev = false; } } void revdata() { rev ^= true; swap(l, r); } inline int pos() { if (p) { if (p->l == this) return -1; if (p->r == this) return 1; } return 0; } void rot() { NP q = p->p; int pps = p->pos(); if (pps == -1) q->l = this; if (pps == 1) q->r = this; if (p->l == this) { p->l = r; if (r) r->p = p; r = p; } else { p->r = l; if (l) l->p = p; l = p; } p->p = this; p->update(); update(); p = q; if (q) q->update(); } void all_push() { if (pos()) p->all_push(); push(); } void splay() { all_push(); int ps; while ((ps = pos())) { int pps = p->pos(); if (!pps) { rot(); } else if (ps == pps) { p->rot(); rot(); } else { rot(); rot(); } } } void expose() { NP u = this, ur = nullptr; do { u->splay(); u->r = ur; u->update(); ur = u; } while ((u = u->p)); splay(); } void link(NP np) { evert(); np->expose(); p = np; } void cut() { expose(); assert(l); l->p = nullptr; l = nullptr; update(); } void evert() { expose(); revdata(); } NP parent() { expose(); NP u = this->l; if (u == nullptr) return nullptr; u->push(); while (u->r != nullptr) { u = u->r; u->push(); } u->expose(); return u; } NP lca(NP n) { n->expose(); expose(); NP t = n; while (n->p != nullptr) { if (!n->pos()) t = n->p; n = n->p; } if (this != n) return nullptr; t->expose(); return t; } }; struct Node { using D = ll; static D e_d() { return 0; } static D op_dd(const D& l, const D& r) { return l + r; } }; int main() { Scanner sc(stdin); Printer pr(stdout); int n; sc.read(n); V> lct(2 * n - 1); for (int i = 0; i < n - 1; i++) { int a, b; ll c; sc.read(a, b, c); lct[n + i].init_node(c); lct[a].link(&(lct[n + i])); lct[n + i].link(&(lct[b])); } int q; sc.read(q); for (int ph = 0; ph < q; ph++) { int ty; sc.read(ty); if (ty == 1) { int u, v, w, x; sc.read(u, v, w, x); lct[v].evert(); lct[u].expose(); auto e = lct[u].parent(); lct[u].cut(); e->cut(); e->init_node(x); lct[w].evert(); lct[w].link(e); e->link(&(lct[v])); } else { function(V)> mysort = [&](V v) { int m = int(v.size()); global_gen.shuffle(v.begin(), v.end()); if (m == 1) return v; int root = v[0]; map p2dps; map> mp; for (int i = 0; i < m; i++) { int trg = v[i]; auto lca = lct[root].lca(&lct[trg]); int lca_id = int(lca - &(lct[0])); if (!p2dps.count(lca_id)) { lct[lca_id].expose(); p2dps[lca_id] = lct[lca_id].sz; } mp[p2dps[lca_id]].push_back(trg); } V res; for (auto p: mp) { p.second = mysort(p.second); for (int d: p.second) res.push_back(d); } return res; }; int k; sc.read(k); V v(k); sc.read(v); v = mysort(v); ll sm = 0; for (int i = 0; i < k; i++) { int x = v[i], y = v[(i + 1) % k]; lct[x].evert(); lct[y].expose(); sm += lct[y].sm; } pr.writeln(sm / 2); } } return 0; }