//#pragma GCC optimize("Ofast") //#pragma GCC target("avx") //#undef LOCAL #include #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) { int len = 0; // Reference and edit: // cpprefjp - C++日本語リファレンス // (https://cpprefjp.github.io/reference/algorithm/shuffle.html) for (auto it = first + 1; it != last; it++) { len++; int j = uniform(0, len); if (j != len) 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; using namespace std; 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 LCNode { using NP = LCNode*; static NP last; //ll d = 0, dsm = 0; ll d, dsm; NP init_last() { sz = 0; // Important d = dsm = 0; return this; } void init_node(ll d) { sz = 1; rev = false; // Important this->d = dsm = d; } void update() { sz = 1 + l->sz + r->sz; // Important dsm = d + l->dsm + r->dsm; } void push() { assert(this != last); if (rev) { // Important if (l != last) { l->revdata(); } if (r != last) { r->revdata(); } rev = false; } } void revdata() { rev ^= true; swap(l, r); // Important } NP p, l, r; int sz; bool rev; LCNode() : p(nullptr), l(last), r(last) {} 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 splay() { supush(); int ps; while ((ps = pos())) { int pps = p->pos(); if (!pps) { rot(); } else if (ps == pps) { p->rot(); rot(); } else { rot(); rot(); } } } void expose() { assert(this != last); NP u = this, ur = last; do { u->splay(); u->r = ur; u->update(); ur = u; } while ((u = u->p)); splay(); } void supush() { if (pos()) p->supush(); push(); } void link(NP r) { evert(); r->expose(); p = r; } void cut() { expose(); l->p = NULL; l = last; update(); } void evert() { expose(); revdata(); } //tree func NP parent() { expose(); NP u = this->l; if (u == last) return last; u->push(); while (u->r != last) { u = u->r; u->push(); } u->expose(); return u; } NP root() { expose(); NP u = this; while (u->l != last) { u = u->l; 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; } return (this == n) ? t : nullptr; } int dps() { expose(); return sz; } }; LCNode::NP LCNode::last = (new LCNode())->init_last(); int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int n; cin >> n; V lct(2 * n - 1); for (int i = 0; i < n; i++) { lct[i].init_node(0); } for (int i = 0; i < n - 1; i++) { int a, b; ll c; cin >> a >> b >> c; lct[n + i].init_node(c); lct[a].evert(); lct[a].link(&(lct[n + i])); lct[n + i].link(&(lct[b])); } int q; cin >> q; for (int ph = 0; ph < q; ph++) { int ty; //cin >> ty; ty = 2; if (ty == 1) { int u, v, w; ll x; cin >> u >> v >> w >> x; lct[v].evert(); lct[u].expose(); auto e = lct[u].parent(); assert(e->parent() == &(lct[v])); 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 = lca - &(lct[0]); if (!p2dps.count(lca_id)) { p2dps[lca_id] = lct[lca_id].dps(); } mp[p2dps[lca_id]].push_back(trg); } V res; for (auto p: mp) { mysort(p.second); for (int d: p.second) res.push_back(d); } return res; }; int k; cin >> k; V v(k); for (int i = 0; i < k; i++) { cin >> v[i]; } 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].dsm; // dbg(x, y, lct[y].dsm); } cout << sm / 2 << "\n"; } } return 0; }