#include #include using i64 = long long; struct cluster { i64 ans; i64 inter; i64 sum; i64 left; i64 right; i64 has; i64 length; using V = std::size_t; cluster(i64 l): ans(0), inter(0), sum(0), left(0), right(0), has(0), length(l) {} static cluster identity() { return cluster(0); } static cluster compress(const cluster& a, const cluster& b, V av, V bv, V cv) { if(a.has == 0 && b.has == 0) { if(cv == 0) { cluster c = identity(); c.ans = (av && bv) * (a.length + b.length); c.length = a.length + b.length; return c; } else { cluster c = identity(); c.ans = av * a.length + bv * b.length; c.left = a.length; c.right = b.length; c.has = 1; c.length = a.length + b.length; return c; } } else if(a.has == 0) { if(cv == 0) { cluster c = identity(); c.inter = b.inter; c.sum = b.sum; c.left = a.length + b.left; c.right = b.right; c.has = 1; c.length = a.length + b.length; c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter; return c; } else { cluster c = identity(); c.inter = 0; c.left = a.length; c.right = b.right; c.has = 1; c.length = a.length + b.length; c.sum = b.sum + b.left + b.inter; c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter; return c; } } else if(b.has == 0) { if(cv == 0) { cluster c = identity(); c.inter = a.inter; c.sum = a.sum; c.left = a.left; c.right = a.right + b.length; c.has = 1; c.length = a.length + b.length; c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter; return c; } else { cluster c = identity(); c.inter = 0; c.left = a.left; c.right = b.length; c.has = 1; c.length = a.length + b.length; c.sum = a.sum + a.right + a.inter; c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter; return c; } } else { cluster c = identity(); c.inter = 0; c.left = a.left; c.right = b.right; c.has = 1; c.length = a.length + b.length; c.sum = a.sum + b.sum + a.right + b.left + a.inter + b.inter; c.ans = av * c.left + bv * c.right + c.sum + (av || bv) * c.inter; return c; } } static cluster rake(const cluster& a, const cluster& b, V av, V bv, V cv) { if(a.has == 0 && b.has == 0) { if(bv == 0) { cluster c = identity(); c.length = a.length; return c; } else { cluster c = identity(); c.inter = b.length; c.left = a.length; c.right = 0; c.has = 1; c.length = a.length; return c; } } else if(a.has == 0) { if(bv == 0) { cluster c = identity(); c.inter = b.inter + b.right; c.sum = b.sum; c.left = a.length; c.right = 0; c.has = 1; c.length = a.length; return c; } else { cluster c = identity(); c.inter = b.inter + b.right; c.sum = b.sum + b.left; c.left = a.length; c.right = 0; c.has = 1; c.length = a.length; return c; } } else if(b.has == 0) { if(bv == 0) { cluster c = identity(); c.inter = a.inter; c.sum = a.sum; c.left = a.left; c.right = a.right; c.has = 1; c.length = a.length; return c; } else { cluster c = identity(); c.inter = 0; c.sum = a.sum + a.inter + a.right + b.length; c.left = a.left; c.right = 0; c.has = 1; c.length = a.length; return c; } } else { cluster c = identity(); c.inter = 0; c.left = a.left; c.right = 0; c.has = 1; c.length = a.length; c.sum = a.sum + b.sum + a.right + b.right + a.inter + b.inter + bv * b.left; return c; } } static cluster reverse(const cluster& c) { cluster res = c; std::swap(res.left, res.right); return res; } static std::size_t select(const cluster& a, const cluster& b, V av, V bv, V cv) { return 0; } }; class vertex; class node; int parent_dir(node*); node* link(vertex, vertex, cluster); void test_comp_set(node* n); class vertex_raw { cluster::V val; node* hand; public: vertex_raw(cluster::V val): val(val), hand(nullptr) {} node* handle() const { return this->hand; } void set_handle(node* hand) { this->hand = hand; } const cluster::V& value() const { return this->val; } void set_value(cluster::V val) { this->val = val; } }; class vertex { vertex_raw* ver; private: public: static vertex dangling() { return vertex(); } vertex(): ver(nullptr) {} vertex(cluster::V val): ver( new vertex_raw(val)) { vertex dummy; dummy.ver = new vertex_raw(cluster::V()); link(*this, dummy, cluster::identity()); } bool operator==(const vertex& other) { return this->ver == other.ver; } inline node* handle() const { return this->ver->handle(); } inline void set_handle(node* hand) { this->ver->set_handle(hand); } inline const cluster::V& value() const { return this->ver->value(); } inline void set_value(cluster::V val) { this->ver->set_value(val); } }; enum class Type { Compress, Rake, Edge, None }; static std::size_t ni = 0; extern node ns[1010101]; class node { node* ch[2]; node* par; node* ra; node* me; bool rev; cluster fo; vertex v[2]; Type ty; public: node(): par(nullptr), ra(nullptr), me(nullptr), rev(false), fo(cluster::identity()), ty(Type::None) {} static node* new_edge(vertex v, vertex u, cluster val) { //node* n = new node(); node* n = ns + (ni++); n->v[0] = v; n->v[1] = u; n->fo = val; n->me = n; n->ty = Type::Edge; n->fix(); return n; } static node* new_compress(node* left, node* right) { //node* n = new node(); node* n = ns + (ni++); n->ch[0] = left; n->ch[1] = right; n->me = n; n->ty = Type::Compress; n->fix(); return n; } static node* new_rake(node* left, node* right) { //node * n = new node(); node* n = ns + (ni++); n->ch[0] = left; n->ch[1] = right; n->me = n; n->ty = Type::Rake; n->fix(); return n; } inline void fix() { if(this->ty == Type::Edge) { if(!this->parent()) { this->endpoint(0).set_handle(this->me); this->endpoint(1).set_handle(this->me); } else if(this->parent()->ty == Type::Compress) { if(parent_dir(this->me) == -1) { this->endpoint(0).set_handle(this->me); } } else if(this->parent()->ty == Type::Rake) { this->endpoint(0).set_handle(this->me); } } else if(this->ty == Type::Compress) { this->push(); this->v[0] = this->child(0)->endpoint(0); this->v[1] = this->child(1)->endpoint(1); assert(this->child(0)->endpoint(1) == this->child(1)->endpoint(0)); cluster left = this->child(0)->fold(); node* l = this->child(0); if(this->rake()) { node* r = this->rake(); left = cluster::rake(l->fold(), r->fold(), l->endpoint(0).value(), r->endpoint(0).value(), l->endpoint(1).value()); } node* r = this->child(1); this->fo= cluster::compress(left, r->fold(), l->endpoint(0).value(), r->endpoint(1).value(), l->endpoint(1).value()); this->child(0)->endpoint(1).set_handle(this->me); if(!this->parent()) { this->endpoint(0).set_handle(this->me); this->endpoint(1).set_handle(this->me); } else if(this->parent()->ty == Type::Compress) { if(parent_dir(this->me) == -1) { this->endpoint(0).set_handle(this->me); } } else if(this->parent()->ty == Type::Rake) { this->endpoint(0).set_handle(this->me); } } else if(this->ty == Type::Rake) { this->push(); this->v[0] = this->child(0)->endpoint(0); this->v[1] = this->child(0)->endpoint(1); this->fo = cluster::rake(this->child(0)->fold(), this->child(1)->fold(), this->child(0)->endpoint(0).value(), this->child(1)->endpoint(0).value(), this->child(0)->endpoint(1).value()); } else { assert(false); } } inline void push() { if(this->ty == Type::Compress) { if(this->rev) { std::swap(this->ch[0], this->ch[1]); this->child(0)->reverse(); this->child(1)->reverse(); this->rev = false; } } } inline void reverse() { if(this->ty == Type::Edge) { std::swap(this->v[0], this->v[1]); this->fo = cluster::reverse(this->fold()); } else if(this->ty == Type::Compress) { std::swap(this->v[0], this->v[1]); this->fo = cluster::reverse(this->fold()); this->rev ^= true; } else if(this->ty == Type::Rake) { } else { assert(false); } } inline node* parent() const { return this->par; } inline void set_parent(node* par) { this->par = par; } inline node* rake() const { return this->ra; } inline void set_rake(node* rake) { this->ra = rake; } inline node* child(std::size_t dir) const { return this->ch[dir]; } inline void set_child(node* ch, std::size_t dir) { this->ch[dir] = ch; } inline vertex endpoint(std::size_t dir) { return this->v[dir]; } inline Type type() const { return this->ty; } cluster fold() const { return this->fo; } bool guard; }; int parent_dir(node* child) { node* par = child->parent(); if(par) { if(par->guard) { return -1; } else if(par->child(0) == child) { return 0; } else if(par->child(1) == child) { return 1; } else { return -1; } } else { return -1; } } int parent_dir_guard(node* child) { node* par = child->parent(); if(par) { if(par->child(0) == child) { return 0; } else if(par->child(1) == child) { return 1; } else { return -1; } } else { return -1; } } void rotate(node* t, node* x, std::size_t dir) { node* y = x->parent(); int par = parent_dir_guard(x); t->child(dir)->push(); x->set_child(t->child(dir), dir ^ 1); t->child(dir)->set_parent(x); t->set_child(x, dir); x->set_parent(t); t->set_parent(y); if(par != -1) { y->set_child(t, par); } else if(y && y->type() == Type::Compress) { y->set_rake(t); } x->fix(); t->fix(); if(y && !y->guard) { y->fix(); } } void splay(node* t) { assert(t->type() != Type::Edge); t->push(); while(parent_dir(t) != -1) { node* q = t->parent(); if(q->type() != t->type()) break; if(parent_dir(q) != -1 && q->parent() && q->parent()->type() == q->type()) { node* r = q->parent(); if(r->parent()) r->parent()->push(); r->push(); q->push(); t->push(); int qt_dir = parent_dir(t); int rq_dir = parent_dir(q); if(rq_dir == qt_dir) { rotate(q, r, rq_dir ^ 1); rotate(t, q, qt_dir ^ 1); } else { rotate(t, q, qt_dir ^ 1); rotate(t, r, rq_dir ^ 1); } } else { if(q->parent()) q->parent()->push(); q->push(); t->push(); int qt_dir = parent_dir(t); rotate(t, q, qt_dir ^ 1); } } } node* expose_raw(node* t) { while(true) { assert(t->type() != Type::Rake); if(t->type() == Type::Compress) { splay(t); } node* n = nullptr; { node* par = t->parent(); if(!par) { break; } else if(par->type() == Type::Rake) { par->push(); splay(par); n = par->parent(); } else if(par->type() == Type::Compress) { par->push(); if(par->guard && parent_dir_guard(t) != -1) { break; } n = par; } else { assert(false); } } splay(n); int dir = parent_dir_guard(n); if(dir == -1 || n->parent()->type() == Type::Rake) dir = 0; if(dir == 1) { n->child(dir)->reverse(); n->child(dir)->push(); t->reverse(); t->push(); } int n_dir = parent_dir(t); if(n_dir != -1) { node* nch = n->child(dir); nch->push(); node* rake = t->parent(); rake->push(); rake->set_child(nch, n_dir); nch->set_parent(rake); n->set_child(t, dir); t->set_parent(n); nch->fix(); rake->fix(); t->fix(); n->fix(); splay(rake); } else { node* nch = n->child(dir); nch->push(); n->set_rake(nch); nch->set_parent(n); n->set_child(t, dir); t->set_parent(n); nch->fix(); t->fix(); n->fix(); } if(t->type() == Type::Edge) { t = n; } } return t; } node* expose(vertex ver) { return expose_raw(ver.handle()); } void soft_expose(vertex v, vertex u) { node* root = expose(v); if(v.handle() == u.handle()) { if(root->endpoint(1) == v || root->endpoint(0) == u) { root->reverse(); root->push(); } return; } root->guard = true; node* soot = expose(u); root->guard = false; root->fix(); if(parent_dir(soot) == 0) { root->reverse(); root->push(); } } node* link(vertex v, vertex u, cluster weight) { if(!v.handle() && !u.handle()) { return node::new_edge(v, u, weight); } else { node* nnu = u.handle(); node* nnv = v.handle(); node* e = node::new_edge(v, u, weight); node* left = nullptr; if(!nnu) { left = e; } else { node* uu = expose_raw(nnu); uu->push(); if(uu->endpoint(1) == u) { uu->reverse(); uu->push(); } if(uu->endpoint(0) == u) { node* nu = node::new_compress(e, uu); e->set_parent(nu); e->fix(); uu->set_parent(nu); uu->fix(); nu->fix(); left = nu; } else { node* nu = uu; node* left_ch = nu->child(0); left_ch->push(); nu->set_child(e, 0); e->set_parent(nu); e->fix(); node* beta = nu->rake(); node* rake = nullptr; if(beta) { beta->push(); rake = node::new_rake(beta, left_ch); beta->set_parent(rake); left_ch->set_parent(rake); beta->fix(); left_ch->fix(); } else { rake = left_ch; } nu->set_rake(rake); rake->set_parent(nu); rake->fix(); nu->fix(); left = nu; } } if(!nnv) {} else { node* vv =expose_raw(nnv); vv->push(); if(vv->endpoint(0) == v) { vv->reverse(); vv->push(); } if(vv->endpoint(1) == v) { node* top = node::new_compress(vv, left); vv->set_parent(top); left->set_parent(top); vv->fix(); left->fix(); top->fix(); } else { node* nv = vv; node* right_ch = nv->child(1); right_ch->reverse(); right_ch->push(); nv->set_child(left, 1); left->set_parent(nv); left->fix(); node* alpha = nv->rake(); node* rake = nullptr; if(alpha) { alpha->push(); rake = node::new_rake(alpha, right_ch); alpha->set_parent(rake); alpha->fix(); right_ch->set_parent(rake); right_ch->fix(); } else { rake = right_ch; } nv->set_rake(rake); rake->set_parent(nv); rake->fix(); nv->fix(); } } return e; } } void bring(node* root) { node* rake = root->rake(); if(!rake) { node* left = root->child(0); //delete root, root = nullptr; left->set_parent(nullptr); left->fix(); } else if(rake->type() == Type::Compress || rake->type() == Type::Edge) { rake->push(); node* new_right = rake; new_right->reverse(); new_right->push(); root->set_child(new_right, 1); new_right->set_parent(root); root->set_rake(nullptr); new_right->fix(); root->fix(); } else if(rake->type() == Type::Rake) { rake->push(); while(rake->child(1)->type() == Type::Rake) { rake->child(1)->push(); rake = rake->child(1); } root->guard = true; splay(rake); root->guard = false; node* new_rake = rake->child(0); node* new_right = rake->child(1); //delete rake, rake = nullptr; new_right->reverse(); new_right->push(); root->set_child(new_right, 1); new_right->set_parent(root); root->set_rake(new_rake); new_rake->set_parent(root); new_rake->fix(); new_right->fix(); root->fix(); } } void cut(vertex v, vertex u) { soft_expose(v, u); node* root = v.handle(); root->push(); node* right = root->child(1); right->set_parent(nullptr); right->reverse(); right->push(); bring(right); bring(root); } cluster path_query(vertex v, vertex u) { soft_expose(v, u); node* root = v.handle(); root->push(); if(root->endpoint(0) == v && root->endpoint(1) == u) { return root->fold(); } else if(root->endpoint(0) == v) { return root->child(0)->fold(); } else if(root->endpoint(1) == u) { return root->child(1)->fold(); } else { root->child(1)->push(); return root->child(1)->child(0)->fold(); } } node* select_rake(node* rake, cluster& right, cluster::V& rv0, cluster::V& rv1) { rake->push(); while(rake->type() == Type::Rake) { node* l = rake->child(0); node* r = rake->child(1); l->push(); r->push(); cluster rf = cluster::rake(r->fold(), right, r->endpoint(0).value(), rv0, r->endpoint(1).value()); cluster::V r0 = r->endpoint(0).value(); std::size_t dir = cluster::select(l->fold(), rf, l->endpoint(0).value(), r0, l->endpoint(1).value()); r = rake->child(1 - dir); rake = rake->child(dir); right = cluster::rake(r->fold(), right, r->endpoint(0).value(), rv0, r->endpoint(1).value()); rv0 = r->endpoint(0).value(); rv1 = r->endpoint(1).value(); rake->push(); } return rake; } std::pair select(vertex v) { node* n = expose(v); cluster lf = cluster::identity(); cluster::V l0, l1; bool luse = false; cluster rf = cluster::identity(); cluster::V r0, r1; bool ruse = false; n->push(); while(n->type() == Type::Compress) { node* a = n->child(0); node* b = n->child(1); node* r = n->rake(); a->push(); b->push(); if(r) { r->push(); } cluster af = a->fold(); cluster::V a0 = a->endpoint(0).value(); cluster::V a1 = a->endpoint(1).value(); if(luse) { af = cluster::compress(lf, af, l0, a1, l1); a0 = l0; a1 = a1; } cluster bf = b->fold(); cluster::V b0 = b->endpoint(0).value(); cluster::V b1 = b->endpoint(1).value(); if(ruse) { bf = cluster::compress(bf, rf, b0, r1, b1); b0 = b0; b1 = r1; } cluster arf = af; if(r) { arf = cluster::rake(af, r->fold(), a0, r->endpoint(0).value(), a1); } std::size_t dir = cluster::select(arf, bf, a0, b1, a1); if(dir == 0) { if(r) { cluster rbf = cluster::reverse(bf); cluster::V rb0 = b1; cluster rrf = cluster::rake(r->fold(), rbf, r->endpoint(0).value(), rb0, r->endpoint(1).value()); cluster::V rr0 = r->endpoint(0).value(); cluster::V rr1 = r->endpoint(1).value(); dir = cluster::select(af, rrf, a0, rr0, a1); if(dir == 0) { rf = cluster::reverse(rrf); r0 = rr1; r1 = rr0; ruse = true; n = n->child(0); } else { luse = false; rf = cluster::rake(af, rbf, a0, rb0, a1); r0 = a0; r1 = a1; ruse = true; n = select_rake(r, rf, r0, r1); rf = cluster::reverse(rf); std::swap(r0, r1); } } else { rf = bf; r0 = b0; r1 = b1; ruse = true; n = n->child(0); } } else { lf = arf; l0 = a0; l1 = a1; luse = true; n = n->child(1); } n->push(); } return { n->endpoint(0), n->endpoint(1) }; } node ns[1010101]; #include #include #include using namespace std; int main() { i64 N; cin >> N; vector vs; for(int i = 0;i < N;i++) { vs.push_back(vertex(0)); } for(int i = 0;i < N - 1;i++) { i64 a, b, c; cin >> a >> b >> c; link(vs[a], vs[b], cluster(c)); } i64 Q; cin >> Q; for(i64 q = 0; q < Q; q++) { i64 type; cin >> type; if(type == 1) { i64 u, v, w, x; cin >> u >> v >> w >> x; cut(vs[u], vs[v]); link(vs[v], vs[w], cluster(x)); } else { i64 k; cin >> k; vector vec(k); for(int i = 0;i < k;i++) cin >> vec[i]; i64 ans = 0; for(auto a: vec) { auto node = expose(vs[a]); vs[a].set_value(1); node->fix(); ans = node->fold().ans; } cout << ans << endl; for(auto a: vec) { auto node = expose(vs[a]); vs[a].set_value(0); node->fix(); } } } }