#line 1 "/home/imsuck/Yes/prog-sol/testing.cpp" #include using namespace std; #line 1 "/home/imsuck/Yes/cp-library/other/types.hpp" using i8 = int8_t; using u8 = uint8_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using f32 = float; using f64 = double; using f80 = long double; using str = string; template using vec = vector; template using graph = vec>; #line 5 "/home/imsuck/Yes/prog-sol/testing.cpp" #line 1 "/home/imsuck/Yes/cp-library/tree/top_tree_ecnerwala.hpp" /** * https://github.com/ecnerwala/cp-book/blob/master/src/top_tree.hpp * Convenient memo: * Creating vertices: * n->val = ...; * n->set_vert(); * * Creating edges: * link(e, va, vb); * * Updates: * auto cur = get_path(va, vb); // or get_subtree(va, vb) * cur->do_stuff(); * cur->pull_all(); * * Node types: * path edges: compress(c[0], self, c[1]) * assert(is_path && !is_vert); * assert(c[0] && c[1]); * assert(c[0]->is_path && c[1]->is_path); * assert(!c[2]); * (path) vertices: add_vertex(self, rake(c[0], c[1])) * assert(is_path && is_vert); * assert(!c[2]); * if (c[0]) assert(!c[0]->is_path); * if (c[1]) assert(!c[1]->is_path); * non-path edges: rake(c[0], add_edge(self, c[2]), c[1]) * assert(!is_path && !is_vert); * assert(c[2]) * assert(c[2]->is_path); * if (c[0]) assert(!c[0]->is_path); * if (c[1]) assert(!c[1]->is_path); */ template struct top_tree_node_base { using ptr = node *; private: ptr as_derived() { return (ptr)this; } auto as_derived() const { return (const ptr)this; } public: bool rev = false; ptr p = 0; array c{0, 0, 0}; int d() const { assert(p); if (this == p->c[0]) return 0; if (this == p->c[1]) return 1; if (this == p->c[2]) return 2; assert(false); } ptr &p_c() { return p->c[d()]; } bool is_vert, is_path; void set_vert() { is_path = is_vert = true, _pull(); } bool r() const { return !p || p->is_path != is_path; } // protected: #define CHECK(a) \ template struct has_##a##_t : false_type {}; \ template struct has_##a##_t> : true_type {}; \ template static constexpr bool has_##a = has_##a##_t::value; CHECK(push) CHECK(flip) CHECK(pull) #undef CHECK void _flip() { assert(is_path); swap(c[0], c[1]), rev ^= 1; if constexpr (has_flip) as_derived()->flip(); } void push_rev() { if (rev) { assert(is_path); if (!is_vert) { c[0]->_flip(); c[1]->_flip(); } rev = false; } } void _push() { push_rev(); if constexpr (has_push) as_derived()->push(); } void _pull() { if constexpr (has_pull) as_derived()->pull(); } public: void push_all() { if (p) p->push_all(); _push(); } void push_flip_all() { if (p) p->push_flip_all(); if (rev) { assert(is_path); if (!is_vert) { c[0]->_flip(); c[1]->_flip(); } rev = false; } } ptr pull_all() { ptr cur = as_derived(); cur->_push(), cur->_pull(); for (; cur->p; cur->_pull()) cur = cur->p; return cur; } private: static inline void attach(ptr pa, int c_d, ptr ch) { pa->c[c_d] = ch; if (ch) ch->p = pa; } void rot() { assert(!is_vert); assert(!r()); ptr pa = p; int x = d(); assert(x != 2); ptr ch = c[!x]; if (pa->p) pa->p_c() = as_derived(); this->p = pa->p; attach(pa, x, ch); attach(as_derived(), !x, pa); pa->_pull(); } void rot2(int c_d) { assert(!is_vert); assert(!r()); assert(c[c_d]); assert(!c[c_d]->is_vert); if (d() == c_d) return rot(); ptr pa = p; int x = d(); assert(x != 2); ptr ch = c[c_d]->c[!x]; if (pa->p) pa->p_c() = as_derived(); this->p = pa->p; attach(pa, x, ch); attach(c[c_d], !x, pa); pa->_pull(); } void splay_dir(int x) { for (; !r() && d() == x; rot()) if (!p->r() && p->d() == x) p->rot(); } void splay() { assert(!is_vert); for (; !r(); rot()) if (!p->r()) p->d() == d() ? p->rot() : rot(); } void splay2(int c_d) { assert(!is_vert && is_path); assert(c[c_d] && !c[c_d]->is_vert); for (; !r(); rot2(c_d)) if (!p->r()) p->d() == d() ? p->rot() : rot2(c_d); } void splay2() { assert(!is_vert && is_path); assert(!r()); p->splay2(d()); } void splay_vert() { assert(is_vert); if (r()) return; p->splay_dir(d()); if (p->r()) return; assert(p->d() != d()); if (d() == 1) p->rot(); assert(d() == 0); p->splay2(); assert(d() == 0); assert(p->d() == 1); assert(p->p->r()); } ptr cut_right() { assert(is_vert && is_path); splay_vert(); if (r() || d() == 1) { assert(r() || (d() == 1 && p->r())); assert(!c[0]); return 0; } ptr pa = p; assert(pa->r() || (pa->d() == 1 && pa->p->r())); assert(!pa->is_vert); assert(pa->is_path); assert(pa->c[0] == this); assert(!pa->c[2]); if (pa->p) pa->p_c() = as_derived(); this->p = pa->p; pa->is_path = false; pa->c[2] = pa->c[1]; attach(pa, 0, c[0]); attach(pa, 1, c[1]); c[0] = 0; attach(as_derived(), 1, pa); assert(!c[2]); return pa->_pull(), pa; } ptr splice_non_path() { assert(!is_vert); assert(!is_path); splay(); assert(p && p->is_vert && p->is_path); p->cut_right(); if (!p->is_path) rot(); assert(p && p->is_vert && p->is_path); assert(p->r() || (p->d() == 1 && p->p->r())); assert(p->c[d()] == this && !p->c[!d()]); ptr pa = p; if (pa->p) pa->p_c() = as_derived(); this->p = pa->p; attach(pa, 0, c[0]); attach(pa, 1, c[1]); assert(c[2] && c[2]->is_path); attach(as_derived(), 0, pa); c[1] = c[2], c[2] = 0; is_path = true; return pa->_pull(), pa; } ptr splice_all() { ptr res = as_derived(); for (ptr cur = as_derived(); cur; cur = cur->p) { if (!cur->is_path) res = cur->splice_non_path(); assert(cur->is_path); } return res; } public: ptr expose() { assert(is_vert); push_all(); ptr res = splice_all(); cut_right(), pull_all(); return res; } ptr expose_edge() { assert(!is_vert); push_all(); ptr v = is_path ? c[1] : c[2]; for (v->_push(); !v->is_vert; v->_push()) v = v->c[0]; ptr res = v->splice_all(); v->cut_right(), v->pull_all(); assert(!p); assert(v == c[1]); return res == v ? as_derived() : res; } ptr meld_path_end() { assert(!p); ptr rt = as_derived(); while (true) { rt->_push(); if (rt->is_vert) break; rt = rt->c[1]; } rt->splay_vert(); if (rt->c[0] && rt->c[1]) { ptr ch = rt->c[1]; while (true) { ch->_push(); if (!ch->c[0]) break; ch = ch->c[0]; } ch->splay(); attach(ch, 0, rt->c[0]), rt->c[0] = 0; ch->_pull(); } else if (rt->c[0]) { rt->c[1] = rt->c[0], rt->c[0] = 0; } return rt->pull_all(); } void evert() { expose(); ptr rt = as_derived(); while (rt->p) { assert(rt->d() == 1); rt = rt->p; } rt->_flip(); rt->meld_path_end(); expose(); assert(!p); } friend void link(ptr e, ptr v, ptr p) { assert(e && v && p); assert(!e->c[0] && !e->c[1] && !e->c[2]); v->evert(), p->expose(); while (p->p) p = p->p; assert(!v->p); e->is_path = true, e->is_vert = false; attach(e, 0, p); attach(e, 1, v); e->_pull(); } friend void link(node &e, node &v, node &p) { link(&e, &v, &p); } // Link v's root as a child of p with edge e // Returns false if they're already in the same subtree friend bool link_root(ptr e, ptr v, ptr p) { assert(e && v && p); assert(!e->c[0] && !e->c[1] && !e->c[2]); v->expose(); p->expose(); while (v->p) v = v->p; while (p->p) p = p->p; if (v == p) return false; e->is_path = true, e->is_vert = false; attach(e, 0, p); attach(e, 1, v); e->_pull(); return true; } friend bool link_root(node &e, node &v, node &p) { return link_root(&e, &v, &p); } friend pair cut(ptr e) { assert(!e->is_vert); e->expose_edge(); assert(!e->p); assert(e->is_path); ptr l = e->c[0], r = e->c[1]; assert(l && r); assert(!e->c[2]); e->c[0] = e->c[1] = 0; l->p = r->p = 0; l->meld_path_end(); return {l, r}; } friend pair cut(node &e) { auto r = cut(&e); return {*r.first, *r.second}; } friend ptr get_path(ptr v) { assert(v->is_vert); v->expose(); if (!v->p) return v; assert(!v->p->p); return v->p; } friend node &get_path(node &v) { return *get_path(&v); } friend ptr get_subtree(ptr v) { return v->expose(), v; } friend node &get_subtree(node &v) { return v.expose(), v; } friend ptr lca(ptr u, ptr v) { if (u == v) return u; u->expose(); auto up = u->p; ptr l = v->expose(); if (u != v && up == u->p && (!up || !up->p)) return 0; return l; } friend ptr lca(node &u, node &v) { return lca(&u, &v); } }; #line 6 "/home/imsuck/Yes/prog-sol/testing.cpp" struct node : top_tree_node_base { bool open = false, has_open = false; i32 weight = 0; i64 path_weight = 0, ans = 0; array lweight{0, 0}; void flip() { swap(lweight[0], lweight[1]); } void pull() { has_open = open; path_weight = 0; lweight.fill(0); ans = 0; for (int z = 0; z <= 2; z++) { if (!c[z]) continue; has_open |= c[z]->has_open; ans += c[z]->ans; } if (!is_vert && is_path) { path_weight = c[0]->path_weight + weight + c[1]->path_weight; for (int z = 0; z < 2; z++) { lweight[z] = c[!z]->has_open ? c[z]->path_weight + weight + c[!z]->lweight[z] : c[z]->lweight[z]; } } else if (!is_path) { ans += c[2]->lweight[0] + c[2]->has_open * weight; } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); i32 n; cin >> n; vector t(2 * n - 1); map, int> edge_id; for (i32 i = 0; i < n; i++) { t[i].set_vert(); } for (i32 i = n; i < 2 * n - 1; i++) { i32 u, v; cin >> u >> v >> t[i].weight; link(t[i], t[u], t[v]); edge_id[minmax(u, v)] = i; } i32 q; cin >> q; while (q--) { i32 op; cin >> op; if (op == 1) { i32 u, v, w, x; cin >> u >> v >> w >> x; auto it = edge_id.find(minmax(u, v)); int z = it->second; edge_id.erase(it); cut(t[z]); t[z].weight = x; link(t[z], t[v], t[w]); edge_id[minmax(v, w)] = z; } else if (op == 2) { int k; cin >> k; vector xs(k); for (int &x : xs) { cin >> x; t[x].expose(); t[x].open = true; t[x].pull_all(); } t[xs[0]].evert(); cout << t[xs[0]].ans << "\n"; for (int x : xs) { t[x].expose(); t[x].open = false; t[x].pull_all(); } } else { assert(false); } } }