#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; template struct LinkCutTree{ using F=function; using S=function; struct Node{ Node *l, *r, *p; int idx; Monoid key, sum; bool rev; int sz; bool is_root(){ return !p || (p->l!=this && p->r!=this); } Node(int idx, const Monoid &key):idx(idx), key(key), sum(key), sz(1), l(nullptr), r(nullptr), p(nullptr), rev(false) {} }; const Monoid M1; const F f; const S s; LinkCutTree():LinkCutTree([](Monoid a, Monoid b){ return a+b;}, [](Monoid a){ return a;}, Monoid()){} LinkCutTree(const F &f, const S &s, const Monoid &M1):f(f), s(s), M1(M1){} Node *make_node(int idx, const Monoid &v=Monoid()){ return new Node(idx, v); } void toggle(Node *t){ assert(t); swap(t->l, t->r); t->sum=s(t->sum); t->rev^=true; } void push(Node *t){ if(t->rev){ if(t->l) toggle(t->l); if(t->r) toggle(t->r); t->rev=false; } } void update(Node *t){ t->sz=1; t->sum=t->key; if(t->l) t->sz+=t->l->sz, t->sum=f(t->l->sum, t->sum); if(t->r) t->sz+=t->r->sz, t->sum=f(t->sum, t->r->sum); } void rotr(Node *t){ auto *x=t->p, *y=x->p; if((x->l=t->r)) t->r->p=x; t->r=x, x->p=t; update(x), update(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; update(y); } } void rotl(Node *t){ auto *x=t->p, *y=x->p; if((x->r=t->l)) t->l->p=x; t->l=x, x->p=t; update(x), update(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; update(y); } } void splay(Node* t){ push(t); while(!t->is_root()){ auto *q=t->p; if(q->is_root()){ push(q), push(t); if(q->l==t) rotr(t); else rotl(t); }else{ auto *r=q->p; push(r), push(q), push(t); if(r->l==q){ if(q->l==t) rotr(q), rotr(t); else rotl(t), rotr(t); }else{ if(q->r==t) rotl(q), rotl(t); else rotr(t), rotl(t); } } } } Node *expose(Node *t){ Node *rp=nullptr; for(Node *cur=t; cur; cur=cur->p){ splay(cur); cur->r=rp; update(cur); rp=cur; } splay(t); return rp; } void link(Node *child, Node *parent){ expose(child); expose(parent); child->p=parent; parent->r=child; update(parent); } void cut(Node *child){ expose(child); auto *parent=child->l; child->l=nullptr; parent->p=nullptr; update(child); } void evert(Node *t){ expose(t); toggle(t); push(t); } Node *lca(Node *u, Node *v){ //if(get_root(u)!=get_root(v)) return nullptr; expose(u); return expose(v); } Node *get_root(Node *x){ expose(x); while(x->l){ push(x); x=x->l; } return x; } Node *get_kth(Node *v, int k){ expose(v); while(v){ push(v); if(v->r && v->r->sz>k){ v=v->r; }else{ if(v->r) k-=v->r->sz; if(k==0) return v; k--; v=v->l; } } return nullptr; } bool comp(Node *u, Node *v, int du, int dv){ auto *p=lca(u, v); if(p==u) return true; else if(p==v) return false; expose(p); int d=p->sum.first; return get_kth(u, 2*(du-d-1))->idx < get_kth(v, 2*(dv-d-1))->idx; } }; int a[100010], b[100010]; ll w[100010]; int main() { int n; scanf("%d", &n); using LCT=LinkCutTree

; auto f=[](P a, P b){ return P(a.first+b.first, a.second+b.second);}; LCT lct(f, [](P a){ return a;}, P(0, 0)); vector nodev(n), nodee(n-1); for(int i=0; i> g(n); map mp; for(int i=0; ib[i]) swap(a[i], b[i]); mp[{a[i], b[i]}]=i; g[a[i]].push_back({b[i], i}); g[b[i]].push_back({a[i], i}); nodee[i]=lct.make_node(n+i, P(1, w[i])); } auto dfs=[&](auto dfs, int u, int p)->void{ for(auto q:g[u]){ if(q.first==p) continue; lct.link(nodee[q.second], nodev[u]); lct.link(nodev[q.first], nodee[q.second]); dfs(dfs, q.first, u); } }; dfs(dfs, 0, -1); int Q; scanf("%d", &Q); for(int i=0; ivi){ e=mp[{vi, ui}]; mp.erase({vi, ui}); }else{ e=mp[{ui, vi}]; mp.erase({ui, vi}); } lct.evert(nodev[vi]); lct.cut(nodev[ui]); nodee[e]->key=P(1, xi); lct.evert(nodev[wi]); lct.link(nodev[wi], nodee[e]); if(vi>wi) swap(vi, wi); mp[{vi, wi}]=e; }else{ int k; scanf("%d", &k); vector vx(k), ind(k); vector vd(k); for(int j=0; jsum.first; } sort(ind.begin(), ind.end(), [&](int x, int y){ return lct.comp(nodev[vx[x]], nodev[vx[y]], vd[x], vd[y]);}); ll ans=0; for(int j=0; jsum.second; } ans/=2; printf("%lld\n", ans); } } return 0; }