//Let's join Kaede Takagaki Fan Club !! #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair P1; typedef pair P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i void dmp(T a){ rep(i,a.size()) cout << a[i] << " "; cout << endl; } template bool chmax(T&a, T b){ if(a < b){ a = b; return 1; } return 0; } template bool chmin(T&a, T b){ if(a > b){ a = b; return 1; } return 0; } template void g(T &a){ cin >> a; } template void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 998244353; template void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } //verified: yosupo judge (x3), AOJ 2450, Hackerrank white falcon, IJPC2012-3A struct dat { int sz; ll sum; //reverseする void rv(){ //lol } }; //自作コンストラクタ dat dt(ll v = 0){ return {1, v}; } //a, b をこの順にマージする dat mrg(dat a, dat b){ return {a.sz+b.sz, a.sum + b.sum}; } struct node{ node *l, *r, *p; int id, rev; dat D, S; node(int i, ll v = 0) : l(0), r(0), p(0), id(i), rev(0){ //Dに実データを持つ D = S = dt(v); } }; inline bool is_root(node *n){ return n -> p == NULL || n -> p -> l != n && n -> p -> r != n; } inline bool left(node *n){ return n == n -> p -> l; } //遅延評価 //push(n)を走らせた後にはn->l と n->r の値は正しく計算されている必要あり inline void push(node *n){ if(n->rev){ swap(n->l, n->r); if(n->l){ n->l->rev ^= 1; n->l->D.rv(); } if(n->r){ n->r->rev ^= 1; n->r->D.rv(); } n->rev = 0; } } //値の再計算 inline void update(node *n){ //最初に遅延評価 push(n); dat slf = n->S; if(n->l) slf = mrg(n->l->D, slf); if(n->r) slf = mrg(slf, n->r->D); n->D = slf; } inline void connect(node *n, node *p, bool l){ (l ? p -> l : p -> r) = n; if(n) n -> p = p; } //rotateが呼ばれる前には関与しているノードの遅延評価をする必要がある inline void rotate(node *n){ node *p = n -> p, *g = p -> p; bool l = left(n); connect(l ? n -> r : n -> l, p, l); if(!is_root(p)) connect(n, g, left(p)); else n -> p = g; connect(p, n, !l); update(p), update(n); } inline void splay(node *n){ if(is_root(n)){ update(n); return; } while(!is_root(n)){ node *p = n -> p, *g = p -> p; //関与する頂点群の遅延評価をする if(!is_root(p)) push(g); push(p), push(n); if(!is_root(p)) rotate(left(n) ^ left(p) ? n : p); rotate(n); } } //返り値はnじゃないよ inline node* expose(node *n){ node *last = NULL; for(node *m = n; m; m = m -> p){ splay(m); m -> r = last; last = m; } splay(n); return last; } inline void link(node *m, node *n){ expose(m), expose(n); m -> p = n; } inline node* find_root(node *n){ if(!n) return (node*)NULL; while(1){ push(n); if(n->r) n = n->r; else break; } return n; } inline node* cut(node *n){ expose(n); node *ret = n -> l; n -> l -> p = NULL; n -> l = NULL; update(n); return find_root(ret); } //nを根に持っていく //updateは必要ない inline void evert(node *n){ expose(n); n->rev ^= 1; n->D.rv(); } //非連結なら-1 int LCA(node *a,node *b){ expose(a); node *ret = expose(b); if(a->p == (node*)NULL) return -1; else return ret->id; } //nを根とするsplay treeのk番目を見つける int get_kth(node *n, int k){ assert(k > 0 && k <= n->D.sz); while(1){ push(n); if(n->l && n->l->D.sz >= k) n = n->l; else{ k -= (n->l ? n->l->D.sz : 0); if(k == 1){ return n->id; } k--; n = n->r; } } } //nから見てa側に1つ進んだ頂点のid int get(node *n, node *a){ expose(n); int todo = n->D.sz + 1; expose(a); return get_kth(a, todo); } //u-v切断: evert(V[u]) cut(V[v]) //u-v接続: evert(V[u]) link(V[u], V[v]) //点更新は: evert(V[v]) update(V[x]) //u-vパスクエリ: evert(V[u]) expose(V[v]) でV[v]->Dを見る const int MAXN = 100005; node *V[MAXN]; int n,q; int main(){ scanf("%d",&n); rep(i,n) V[i] = new node(i); int eid = 0; rep(i, n-1){ int u, v, w; scanf("%d%d%d",&u, &v, &w); node *mid = new node(eid++, w); evert(V[u]); link(V[u], mid); link(mid, V[v]); } scanf("%d",&q); rep(i, q){ int ty; scanf("%d", &ty); if(ty == 1){ int u, v, w, x; scanf("%d%d%d%d",&u, &v, &w, &x); evert(V[v]); node *mid = cut(V[u]); evert(mid); cut(V[v]); node *nwmid = new node(eid++, x); evert(V[v]); link(V[v], nwmid); link(nwmid, V[w]); } else{ int k; scanf("%d",&k); ll ret = 0; vectorvi(k); rep(i, k) scanf("%d",&vi[i]); sort(vi.begin(), vi.end(), [&](int a, int b){ int c = LCA(V[a], V[b]); assert(c >= 0); if(a == c) return true; if(b == c) return false; return get(V[c], V[a]) < get(V[c], V[b]); }); rep(i, k){ int u = vi[i], v = vi[(i+1)%k]; evert(V[u]); expose(V[v]); ret += V[v]->D.sum; } printf("%lld\n", ret/2); } } }