#include int ri() { int n; scanf("%d", &n); return n; } struct LCT { #define l ch[0] #define r ch[1] struct Node { Node *p; Node *ch[2]; int len_sum; int64_t sum; int len; int val; int size; int index; bool rev; void flush() { if (rev) { l->rev ^= 1; r->rev ^= 1; std::swap(l, r); rev = false; } } void fetch() { len_sum = len + l->len_sum + r->len_sum; sum = val + l->sum + r->sum; size = 1 + l->size + r->size; } void rotate(int dir) { Node *new_root = ch[!dir]; ch[!dir] = new_root->ch[dir]; ch[!dir]->p = this; new_root->ch[dir] = this; if (p->l == this) p->l = new_root; else if (p->r == this) p->r = new_root; new_root->p = p; p = new_root; fetch(); new_root->fetch(); } bool is_root() { return p == LCT::NONE || (p->l != this && p->r != this); } void splay() { flush(); while (!is_root()) { if (p->is_root()) { p->flush(), flush(); p->rotate(p->l == this); } else { Node *pp = p->p; pp->flush(), p->flush(), flush(); bool flag1 = pp->l == p; bool flag2 = p->l == this; if (flag1 == flag2) pp->rotate(flag1); p->rotate(flag2); if (flag1 != flag2) pp->rotate(flag1); } } } }; Node *expose(Node *start) { Node *prev = NONE; for (Node *cur = start; cur != NONE; cur = cur->p) { cur->splay(); cur->r = prev; cur->fetch(); prev = cur; } start->splay(); return prev; } void link(Node *child, Node *parent) { expose(child); expose(parent); child->p = parent; parent->r = child; parent->fetch(); } void cut(Node *child) { expose(child); Node *parent = child->l; parent->p = NONE; child->l = NONE; child->fetch(); } void evert(Node *root) { expose(root); root->rev ^= 1; root->flush(); } Node *root(Node *node) { expose(node); for (; node->flush(), (node->l != NONE); node = node->l); node->splay(); return node; } Node *lca(Node *a, Node *b) { if (root(a) != root(b)) return NONE; expose(a); return expose(b); } Node *climb(Node *node, int dist) { expose(node); while (dist) { if (dist > 0) (node = node->l)->flush(), dist -= node->r->size + 1; else (node = node->r)->flush(), dist += node->l->size + 1; } node->splay(); return node; } #undef l #undef r static Node *nodes, *NONE; static int head; LCT () { if (!head) nodes[head++] = {NONE, {NONE, NONE}, 0, 0, 0, 0, 0, -1, false}; } Node *new_node(int len, int val, int index) { return &(nodes[head++] = {NONE, {NONE, NONE}, len, val, len, val, 1, index, false}); } }; LCT::Node *LCT::nodes = (Node *) malloc(sizeof(Node) * 1000000), *LCT::NONE = nodes; int LCT::head = 0; int main() { int n = ri(); std::map, int> hens; for (int i = 0; i + 1 < n; i++) { int a = ri(); int b = ri(); int c = ri(); if (a > b) std::swap(a, b); hens[{a, b}] = c; } using Node = LCT::Node; LCT tree; Node *nodes[2 * n - 1]; for (int i = 0; i < n; i++) nodes[i] = tree.new_node(0, 0, i); int cnt = n; for (auto i : hens) { tree.evert(nodes[i.first.first]); tree.evert(nodes[i.first.second]); nodes[cnt] = tree.new_node(1, i.second, -1); tree.link(nodes[i.first.first], nodes[cnt]); tree.link(nodes[i.first.second], nodes[cnt]); cnt++; } auto comp = [&] (int i, int j) { Node *lca = tree.lca(nodes[i], nodes[j]); if (lca == nodes[i]) return false; if (lca == nodes[j]) return true; tree.evert(lca); tree.expose(nodes[i]); int i_dist = nodes[i]->len_sum; tree.expose(nodes[j]); int j_dist = nodes[j]->len_sum; tree.evert(nodes[0]); i = tree.climb(nodes[i], (i_dist - 1) * 2)->index; j = tree.climb(nodes[j], (j_dist - 1) * 2)->index; return i < j; }; int q = ri(); for (int i = 0; i < q; i++) { tree.evert(nodes[0]); if (ri() == 1) { int r0 = ri(); int r1 = ri(); int r2 = ri(); int val = ri(); tree.evert(nodes[r0]); Node *hen = tree.climb(nodes[r1], 1); tree.expose(nodes[r1]); tree.cut(hen); tree.cut(nodes[r1]); hen->val = hen->sum = val; tree.evert(nodes[r2]); tree.link(nodes[r2], hen); tree.link(hen, nodes[r1]); } else { int k = ri(); int b[k]; for (auto &j : b) j = ri(); std::sort(b, b + k, comp); int64_t res = 0; for (int j = 0; j < k; j++) { int next = (j + 1) % k; tree.evert(nodes[b[j]]); tree.expose(nodes[b[next]]); res += nodes[b[next]]->sum; } printf("%lld\n", (long long) (res / 2)); } } return 0; }