結果
| 問題 | No.902 Query ζone |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2022-01-18 00:11:28 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,154 ms / 5,000 ms |
| コード長 | 31,728 bytes |
| コンパイル時間 | 1,478 ms |
| コンパイル使用メモリ | 96,472 KB |
| 実行使用メモリ | 33,920 KB |
| 最終ジャッジ日時 | 2024-11-23 13:03:16 |
| 合計ジャッジ時間 | 18,680 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 6 ms
5,248 KB |
| testcase_02 | AC | 6 ms
5,248 KB |
| testcase_03 | AC | 6 ms
5,248 KB |
| testcase_04 | AC | 6 ms
5,248 KB |
| testcase_05 | AC | 7 ms
5,248 KB |
| testcase_06 | AC | 1,077 ms
33,920 KB |
| testcase_07 | AC | 1,091 ms
33,920 KB |
| testcase_08 | AC | 1,102 ms
33,920 KB |
| testcase_09 | AC | 1,135 ms
33,792 KB |
| testcase_10 | AC | 1,102 ms
33,920 KB |
| testcase_11 | AC | 1,106 ms
33,792 KB |
| testcase_12 | AC | 1,099 ms
33,920 KB |
| testcase_13 | AC | 1,143 ms
33,920 KB |
| testcase_14 | AC | 1,116 ms
33,920 KB |
| testcase_15 | AC | 1,147 ms
33,920 KB |
| testcase_16 | AC | 1,154 ms
33,920 KB |
| testcase_17 | AC | 1,150 ms
33,920 KB |
| testcase_18 | AC | 1,147 ms
33,920 KB |
| testcase_19 | AC | 1,141 ms
33,920 KB |
ソースコード
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>
#include <string>
#include <iostream>
template<
class TopTreeVertexData,
class TopTreeClusterData,
class TopTreeClusterEffect
>
struct TopTree{
public:
struct TopTreeNode;
struct UnderlyingTreeVertex;
private:
void soft_expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){
r->exposing_target();
auto n_l = l->handle;
auto n_r = r->handle;
if(n_l == n_r){
if(n_r->boundary_left == r || n_r->boundary_right == l){
n_r->reverse_boundary_vertices();
n_r->lazy_propagation();
}
}
else{
l->exposing_source(r);
n_r = r->handle;
if(n_r->right_child == n_l) n_r->reverse_boundary_vertices();
n_r->lazy_propagation();
n_l->lazy_propagation();
}
}
void undo_hard_expose(){
for(int i=hard_expose_new_rakes_length-1; i>=0; i--){
hard_expose_new_rakes[i].first->lazy_propagation();
}
for(int i=hard_expose_new_rakes_length-1; i>=0; i--){
if(hard_expose_new_rakes[i].second) delete(hard_expose_new_rakes[i].first);
}
hard_expose_new_rakes_length = 0;
for(int i=0; i<hard_expose_undo_length; i++){
hard_expose_undo_memo[i].execute();
}
hard_expose_undo_length = 0;
}
public:
struct TopTreeNode{
public:
TopTreeNode* parent = nullptr;
TopTreeNode* right_child = nullptr;
TopTreeNode* left_child = nullptr;
TopTreeNode* mid_child = nullptr;
UnderlyingTreeVertex* boundary_left = nullptr;
UnderlyingTreeVertex* boundary_right = nullptr;
bool bouundary_vertices_are_reversed = false;
enum TopTreeNodeType { NODE_TYPE_DISABLED, NODE_TYPE_EDGE, NODE_TYPE_RAKE, NODE_TYPE_COMPRESS };
TopTreeNodeType node_type = NODE_TYPE_DISABLED;
TopTreeClusterData data = TopTreeClusterData::init();
TopTreeClusterEffect lazy_data = TopTreeClusterEffect::id();
void get_propagated(){
TopTreeNode* pp = parent;
TopTreeNode* p = this;
TopTreeNode* tmp = nullptr;
p->parent = nullptr;
while(pp){
tmp = pp->parent;
pp->parent = p;
p = pp;
pp = tmp;
}
while(p){
p->lazy_propagation();
tmp = p->parent;
p->parent = pp;
pp = p;
p = tmp;
}
}
private:
void disable(){
node_type = NODE_TYPE_DISABLED;
parent = nullptr;
left_child = nullptr;
right_child = nullptr;
mid_child = nullptr;
boundary_left = nullptr;
boundary_right = nullptr;
bouundary_vertices_are_reversed = false;
}
TopTreeNode*& parentchild(){
TopTreeNode* p = parent;
if(p->left_child == this) return p->left_child;
if(p->right_child == this) return p->right_child;
if(p->mid_child == this) return p->mid_child;
exit(1);
}
public:
void block(){
if(left_child) left_child->parent = nullptr;
if(right_child) right_child->parent = nullptr;
if(mid_child) mid_child->parent = nullptr;
}
void unblock(TopTreeNode* new_root){
if (left_child && !left_child->is_root()) left_child = new_root;
if (right_child && !right_child->is_root()) right_child = new_root;
if (mid_child && !mid_child->is_root()) mid_child = new_root;
if(node_type == NODE_TYPE_COMPRESS){
bottomup_compress(left_child, mid_child, right_child);
}
if(node_type == NODE_TYPE_RAKE){
bottomup_rake(left_child, right_child);
}
}
void reverse_boundary_vertices(){
bouundary_vertices_are_reversed = !bouundary_vertices_are_reversed;
std::swap(boundary_left, boundary_right);
data.reverse();
if(node_type == NODE_TYPE_COMPRESS){
std::swap(left_child, right_child);
}
}
void apply_lazy_data(TopTreeClusterEffect f){
lazy_data = TopTreeClusterEffect::composition(f, lazy_data);
data = TopTreeClusterEffect::mapping_cluster(f, data);
}
void lazy_propagation(){
if(bouundary_vertices_are_reversed){
if(node_type == NODE_TYPE_COMPRESS){
left_child->reverse_boundary_vertices();
right_child->reverse_boundary_vertices();
}
}
bouundary_vertices_are_reversed = false;
auto f = lazy_data;
if(node_type == NODE_TYPE_COMPRESS){
left_child->apply_lazy_data(f);
if(mid_child){
mid_child->apply_lazy_data(f);
mid_child->boundary_left->data = TopTreeClusterEffect::mapping_vertex(f, mid_child->boundary_left->data);
}
right_child->apply_lazy_data(f);
left_child->boundary_right->data = TopTreeClusterEffect::mapping_vertex(f, left_child->boundary_right->data);
}
if(node_type == NODE_TYPE_RAKE){
left_child->apply_lazy_data(f);
right_child->apply_lazy_data(f);
right_child->boundary_left->data = TopTreeClusterEffect::mapping_vertex(f, right_child->boundary_left->data);
}
lazy_data = TopTreeClusterEffect::id();
}
void bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, TopTreeClusterData x){
node_type = NODE_TYPE_EDGE;
left_child = nullptr;
right_child = nullptr;
mid_child = nullptr;
boundary_left = l;
boundary_right = r;
l->handle = this;
r->handle = this;
data = x;
lazy_data = TopTreeClusterEffect::id();
}
void bottomup_rake(TopTreeNode* l, TopTreeNode* r, bool special_for_hard_expose = false){
if(l->node_type != NODE_TYPE_RAKE) l->boundary_left->handle = l;
if(r->node_type != NODE_TYPE_RAKE) r->boundary_left->handle = r;
if (!special_for_hard_expose) {
node_type = NODE_TYPE_RAKE;
boundary_left = l->boundary_left;
boundary_right = l->boundary_right;
left_child = l;
l->parent = this;
mid_child = nullptr;
right_child = r;
r->parent = this;
data = TopTreeClusterData::rake(left_child->data, right_child->data, right_child->boundary_left->data);
}
else {
node_type = NODE_TYPE_RAKE;
boundary_left = l->boundary_left;
boundary_right = l->boundary_right;
left_child = l;
l->parent = this;
mid_child = nullptr;
right_child = r;
r->parent = this;
auto buf = left_child->data;
buf.reverse();
buf = TopTreeClusterData::rake(buf, right_child->data, right_child->boundary_left->data);
buf.reverse();
data = buf;
}
}
void bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r){
assert(l->boundary_right == r->boundary_left);
UnderlyingTreeVertex* bound = l->boundary_right;
node_type = NODE_TYPE_COMPRESS;
boundary_left = l->boundary_left;
boundary_right = r->boundary_right;
left_child = l;
l->parent = this;
mid_child = m_rake;
if(m_rake) m_rake->parent = this;
right_child = r;
r->parent = this;
if(mid_child && mid_child->node_type != NODE_TYPE_RAKE) mid_child->boundary_left->handle = mid_child;
boundary_left->handle = this;
bound->handle = this;
boundary_right->handle = this;
auto cent = left_child->boundary_right;
auto l_data = left_child->data;
if (mid_child) l_data = TopTreeClusterData::rake(l_data, mid_child->data, mid_child->boundary_left->data);
data = TopTreeClusterData::compress(l_data, cent->data, right_child->data);
}
void rotate_rake_left(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto c1 = left_child;
p->bottomup_rake(p->left_child, c1);
bottomup_rake(p, right_child);
}
void rotate_rake_right(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto c1 = right_child;
p->bottomup_rake(c1, p->right_child);
bottomup_rake(left_child, p);
}
void rotate_compress_left(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto c4 = this->left_child;
p->bottomup_compress(p->left_child, p->mid_child, c4);
bottomup_compress(p, mid_child, right_child);
}
void rotate_compress_right(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto c3 = this->right_child;
p->bottomup_compress(c3, p->mid_child, p->right_child);
bottomup_compress(left_child, mid_child, p);
}
void splay_soft_rake(){
while(!is_rake_root()){
auto p = parent;
if(p->is_rake_root()){
if(p->left_child == this){ rotate_rake_right(); }
else{ rotate_rake_left(); }
}
else{
auto pp = p->parent;
if(p->left_child == this){
if(pp->left_child == p){ p->rotate_rake_right(); rotate_rake_right(); }
else { rotate_rake_right(); rotate_rake_left(); }
}
else{
if(pp->right_child == p){ p->rotate_rake_left(); rotate_rake_left(); }
else { rotate_rake_left(); rotate_rake_right(); }
}
}
}
}
void splay_rake(){
if(is_rake_root()) return;
auto p1 = parent;
p1->splay_soft_rake();
auto p2 = parent;
if(p2 == p1) return;
p2->splay_soft_rake();
}
void splay_compress(){
while(!is_compress_root()){
auto p = parent;
if(p->is_compress_root()){
if(p->left_child == this){ rotate_compress_right(); }
else{ rotate_compress_left(); }
}
else{
auto pp = p->parent;
if(p->left_child == this){
if(pp->left_child == p){ p->rotate_compress_right(); rotate_compress_right(); }
else { rotate_compress_right(); rotate_compress_left(); }
}
else{
if(pp->right_child == p){ p->rotate_compress_left(); rotate_compress_left(); }
else { rotate_compress_left(); rotate_compress_right(); }
}
}
}
}
void splice(bool compress_on_left = true){
TopTreeNode* p = nullptr;
TopTreeNode* rake_l = nullptr;
TopTreeNode* rake_lp = nullptr;
TopTreeNode* rake_r = nullptr;
TopTreeNode* rake_rp = nullptr;
p = parent;
bool is_this_left_child = (p->left_child == this);
while(p->node_type == NODE_TYPE_RAKE){
if(is_this_left_child){
rake_r = p->right_child;
rake_rp = p;
}
else{
rake_l = p->left_child;
rake_lp = p;
}
auto pp = p->parent;
is_this_left_child = (pp->left_child == p);
p = pp;
}
if(compress_on_left){
auto rake_r1 = p->left_child;
if(rake_l){ rake_lp->bottomup_rake(rake_l, rake_r1); rake_r1 = rake_lp; }
if(rake_r){ rake_rp->bottomup_rake(rake_r1, rake_r); rake_r1 = rake_rp; }
p->bottomup_compress(this, rake_r1, p->right_child);
}
else{
reverse_boundary_vertices();
auto rake_r1 = p->right_child;
rake_r1->reverse_boundary_vertices();
if(rake_l){ rake_lp->bottomup_rake(rake_l, rake_r1); rake_r1 = rake_lp; }
if(rake_r){ rake_rp->bottomup_rake(rake_r1, rake_r); rake_r1 = rake_rp; }
p->bottomup_compress(p->left_child, rake_r1, this);
}
}
bool is_enabled() const { return node_type != NODE_TYPE_DISABLED; }
bool is_rake_root() const { return !parent || parent->node_type != NODE_TYPE_RAKE; }
bool is_compress_root() const {
if(!parent) return true;
if(parent->node_type != NODE_TYPE_COMPRESS) return true;
return parent->mid_child == this;
}
bool is_root() const { return !parent; }
};
struct UnderlyingTreeVertex{
TopTreeNode* handle;
TopTreeVertexData data;
UnderlyingTreeVertex(){
handle = nullptr;
data = TopTreeVertexData::init();
}
void exposing_target(){
TopTreeNode* n_this = handle;
handle->get_propagated();
auto c = n_this;
while(!c->is_root()){
if(!c->is_compress_root()){
c->splay_compress();
continue;
}
if(!c->is_rake_root()){
c->splay_rake();
while(!c->is_rake_root()) c = c->parent;
continue;
}
c = c->parent;
}
c = n_this = handle;
while(!c->is_root()){
c->splice();
c = c->parent;
}
handle->get_propagated();
handle->splay_compress();
}
bool exposing_source(UnderlyingTreeVertex* target){
auto n_this = handle;
auto n_target = target->handle;
if(n_this == n_target) return true;
if(n_target->node_type == TopTreeNode::NODE_TYPE_EDGE) return false;
if(n_this->is_root()) return false;
if(n_target->boundary_left == target) n_target->reverse_boundary_vertices();
if(n_target->boundary_right == target){
exposing_target();
return true;
}
handle->get_propagated();
// block
n_target->left_child->parent = nullptr;
n_target->right_child->parent = nullptr;
auto c = n_this;
while(!c->is_root()){
if(!c->is_compress_root()){
c->splay_compress();
continue;
}
if(!c->is_rake_root()){
c->splay_rake();
while(!c->is_rake_root()) c = c->parent;
continue;
}
c = c->parent;
}
if (!n_target->left_child->is_root()) n_target->left_child = c;
if (!n_target->right_child->is_root()) n_target->right_child = c;
c = n_this = handle;
while(!c->is_root()){
auto p = c;
while(!p->is_rake_root()) p = p->parent;
bool compress_to_left = true;
if(n_target->right_child == p->parent) compress_to_left = false;
c->splice(compress_to_left);
c = c->parent;
if(n_target == c){
n_target->left_child->parent = nullptr;
n_target->right_child->parent = nullptr;
}
}
c = handle;
c->get_propagated();
c->splay_compress();
if (!n_target->left_child->is_root()) n_target->left_child = c;
if (!n_target->right_child->is_root()) n_target->right_child = c;
n_target->bottomup_compress(n_target->left_child, n_target->mid_child, n_target->right_child);
if(c->is_root()) return false;
if(n_target->right_child == c){
n_target->reverse_boundary_vertices();
n_target->lazy_propagation();
}
return true;
}
};
TopTreeNode* expose(UnderlyingTreeVertex* l){
undo_hard_expose();
if(!l->handle) return nullptr;
UnderlyingTreeVertex* r = nullptr;
if(l->handle->boundary_left != l) r = l->handle->boundary_left;
if(l->handle->boundary_right != l) r = l->handle->boundary_right;
return expose(l, r);
}
TopTreeNode* expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, bool do_hard = true){
undo_hard_expose();
// soft expose
soft_expose(l, r);
auto n_l = l->handle;
auto n_r = r->handle;
// hard expose
if(do_hard){
auto hard_expose_rake_case1 = [this](TopTreeNode* c)->void {
hard_expose_undo_memo[hard_expose_undo_length++] = HardExposeUndoUnit(c);
hard_expose_undo_memo[hard_expose_undo_length - 1].r_reversed = true;
c->right_child->reverse_boundary_vertices();
TopTreeNode* rake_r = c->right_child;
if(c->mid_child){
auto tmp = new TopTreeNode();
tmp->bottomup_rake(c->mid_child, rake_r);
rake_r = tmp;
hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(rake_r, true);
}
c->bottomup_rake(c->left_child, rake_r, false);
hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(c, false);
};
auto hard_expose_rake_case2 = [this](TopTreeNode* c)->void {
hard_expose_undo_memo[hard_expose_undo_length++] = HardExposeUndoUnit(c);
TopTreeNode* rake_r = c->left_child;
if(c->mid_child){
auto tmp = new TopTreeNode();
tmp->bottomup_rake(rake_r, c->mid_child);
rake_r = tmp;
hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(rake_r, true);
}
c->bottomup_rake(c->right_child, rake_r, true);
hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(c, false);
};
n_r->lazy_propagation();
n_l->lazy_propagation();
if(n_r->boundary_left == l && n_r->boundary_right == r){ /* case (3) (4) do nothing */ }
else if(n_r->boundary_left == l){ /* case (1) */ hard_expose_rake_case1(n_r); }
else if(n_r->boundary_right == r){ /* case (2) */ hard_expose_rake_case2(n_r); }
else{ /* case (5) */ hard_expose_rake_case2(n_l); hard_expose_rake_case1(n_r); }
}
return n_r;
}
bool cut(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, TopTreeClusterData* data_out){
undo_hard_expose();
auto fix_tmporary_state = [this](TopTreeNode* c)->TopTreeNode*{
if(c->mid_child){
if(c->mid_child->node_type == TopTreeNode::NODE_TYPE_RAKE){
// case (3)
auto most_left_rake = c->mid_child;
most_left_rake->lazy_propagation();
while(most_left_rake->left_child->node_type == TopTreeNode::NODE_TYPE_RAKE){
most_left_rake = most_left_rake->left_child;
most_left_rake->lazy_propagation();
}
most_left_rake->splay_soft_rake();
most_left_rake = most_left_rake->left_child;
most_left_rake->reverse_boundary_vertices();
c->bottomup_compress(c->left_child, c->mid_child->right_child, most_left_rake);
}
else{
// case (2)
c->mid_child->reverse_boundary_vertices();
c->bottomup_compress(c->left_child, nullptr, c->mid_child);
}
}
else{
// case (1)
auto cc = c->left_child;
cc->parent = nullptr;
delete(c);
c = cc;
c->boundary_left->handle = c;
c->boundary_right->handle = c;
}
return c;
};
soft_expose(l, r);
auto n_l = l->handle;
auto n_r = r->handle;
if(n_r->node_type == TopTreeNode::NODE_TYPE_EDGE){
// case (4)
l->handle = r->handle = nullptr;
if(data_out) *data_out = n_l->data;
delete(n_l);
return true;
}
if(n_r->boundary_left == l && n_r->boundary_right == r){
// case (3)
return false;
}
if(n_r->boundary_left == l){
// case (1)
n_r->reverse_boundary_vertices();
std::swap(l, r);
// reduce to case (2)
}
if(n_r->boundary_right == r){
// case (2)
n_r->lazy_propagation();
auto lr = n_r->right_child;
if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;
if(data_out) *data_out = lr->data;
delete(lr);
n_r->right_child = nullptr;
fix_tmporary_state(n_r);
r->handle = nullptr;
return true;
}
// case (5)
n_r->lazy_propagation();
n_l->lazy_propagation();
auto lr = n_l->right_child;
if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;
if(data_out) *data_out = lr->data;
delete(lr);
n_r->left_child = nullptr;
n_l->right_child = nullptr;
n_l->parent = nullptr;
fix_tmporary_state(n_l);
n_r->left_child = n_r->right_child;
n_r->left_child->reverse_boundary_vertices();
fix_tmporary_state(n_r);
return true;
}
bool link(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, TopTreeClusterData x){
undo_hard_expose();
auto make_temporary_state = [this](UnderlyingTreeVertex* c)->TopTreeNode* {
auto n_c = c->handle;
if(n_c->boundary_left == c){
n_c->reverse_boundary_vertices();
}
if(n_c->boundary_right == c){
// c is a leaf
auto unstable_root = new TopTreeNode();
n_c->parent = unstable_root;
unstable_root->left_child = n_c;
return unstable_root;
}
// c is not a leaf
n_c->lazy_propagation();
auto r_rake = n_c->right_child;
n_c->right_child = nullptr;
r_rake->reverse_boundary_vertices();
if(n_c->mid_child){
auto rake_root = new TopTreeNode();
rake_root->bottomup_rake(n_c->mid_child, r_rake);
r_rake = rake_root;
}
n_c->mid_child = r_rake;
r_rake->parent = n_c;
n_c->node_type = TopTreeNode::NODE_TYPE_DISABLED;
return n_c;
};
if(!l->handle) std::swap(l, r);
if(!l->handle){
// cut case (4)
TopTreeNode* c = new TopTreeNode();
c->bottomup_edge(l, r, x);
return true;
}
if(!r->handle){
// r->handle == nullptr : cut case (2)
l->exposing_target();
auto n_l = make_temporary_state(l);
auto lr = new TopTreeNode();
lr->bottomup_edge(l, r, x);
n_l->bottomup_compress(n_l->left_child, n_l->mid_child, lr);
return true;
}
// cut case (5)
l->exposing_target();
r->exposing_target();
if(l->handle == r->handle) return false;
if(!l->handle->is_root()) return false;
auto n_l = make_temporary_state(l);
auto n_r = make_temporary_state(r);
std::swap(n_r->left_child, n_r->right_child);
n_r->right_child->reverse_boundary_vertices();
auto lr = new TopTreeNode();
lr->bottomup_edge(l, r, x);
n_r->bottomup_compress(lr, n_r->mid_child, n_r->right_child);
n_l->bottomup_compress(n_l->left_child, n_l->mid_child, n_r);
return true;
}
struct HardExposeUndoUnit{
TopTreeNode* to = nullptr;
TopTreeNode* l = nullptr;
bool l_reversed = false;
TopTreeNode* m_rake = nullptr;
bool m_rake_reversed = false;
TopTreeNode* r = nullptr;
bool r_reversed = false;
HardExposeUndoUnit(){}
HardExposeUndoUnit(TopTreeNode* v){
to = v;
l = v->left_child;
m_rake = v->mid_child;
r = v->right_child;
}
void execute(){
if (l_reversed) l->reverse_boundary_vertices();
if (m_rake_reversed) m_rake->reverse_boundary_vertices();
if (r_reversed) r->reverse_boundary_vertices();
to->bottomup_compress(l, m_rake, r);
}
};
int hard_expose_undo_length = 0;
HardExposeUndoUnit hard_expose_undo_memo[2];
int hard_expose_new_rakes_length = 0;
std::pair<TopTreeNode*, bool> hard_expose_new_rakes[10] = {};
};
struct ios_do_not_sync{
ios_do_not_sync(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
}
} ios_do_not_sync_instance;
using u64 = unsigned long long;
struct TopTreeVertexData{
bool has_on;
static TopTreeVertexData init(){ return { false }; }
};
struct TopTreeClusterData{
u64 on_if_landr;
u64 on_if_l;
u64 on_if_r;
u64 on_if_lorr;
u64 on;
bool has_on;
static TopTreeClusterData edge(u64 w){
TopTreeClusterData res;
res.on_if_landr = w;
res.on_if_l = res.on_if_r = res.on_if_lorr = res.on = 0;
res.has_on = false;
return res;
}
void print(){
using std::cout;
cout << "(" << on_if_landr << "," << on_if_l << "," << on_if_r << "," << on_if_lorr << "," << on << "," << has_on << ")";
}
static TopTreeClusterData init(){ return { 0,0,0,0,0,false }; }
static TopTreeClusterData compress(TopTreeClusterData l, TopTreeVertexData mid, TopTreeClusterData r){
TopTreeClusterData res = init();
bool on_r = mid.has_on || r.has_on;
bool on_l = mid.has_on || l.has_on;
res.has_on = mid.has_on || r.has_on || l.has_on;
u64 voidw = 0;
(on_r ? res.on_if_l : res.on_if_landr) += l.on_if_landr;
res.on_if_l += l.on_if_l;
(on_r ? res.on : res.on_if_r) += l.on_if_r;
(on_r ? res.on : res.on_if_lorr) += l.on_if_lorr;
res.on += l.on;
(on_l ? res.on_if_r : res.on_if_landr) += r.on_if_landr;
(on_l ? res.on : res.on_if_l) += r.on_if_l;
res.on_if_r += r.on_if_r;
(on_l ? res.on : res.on_if_lorr) += r.on_if_lorr;
res.on += r.on;
return res;
}
static TopTreeClusterData rake(TopTreeClusterData l, TopTreeClusterData r, TopTreeVertexData r_end){
TopTreeClusterData res = init();
bool on_r = r_end.has_on || r.has_on;
res.has_on = r_end.has_on || r.has_on || l.has_on;
u64 voidw = 0;
(on_r ? res.on_if_l : res.on_if_landr) += l.on_if_landr;
res.on_if_l += l.on_if_l;
(on_r ? res.on : res.on_if_r) += l.on_if_r;
(on_r ? res.on : res.on_if_lorr) += l.on_if_lorr;
res.on += l.on;
if(l.has_on){
(r_end.has_on ? res.on : voidw) += r.on_if_landr;
(r_end.has_on ? res.on : voidw) += r.on_if_l;
res.on += r.on_if_r;
res.on += r.on_if_lorr;
res.on += r.on;
}
else{
(r_end.has_on ? res.on_if_lorr : voidw) += r.on_if_landr;
(r_end.has_on ? res.on : voidw) += r.on_if_l;
res.on_if_lorr += r.on_if_r;
(r_end.has_on ? res.on : res.on_if_lorr) += r.on_if_lorr;
res.on += r.on;
}
return res;
}
void reverse(){
std::swap(on_if_l, on_if_r);
}
};
struct TopTreeClusterEffect{
static TopTreeClusterEffect id(){ return { }; }
static TopTreeClusterData mapping_cluster(TopTreeClusterEffect f, TopTreeClusterData x){
return x;
}
static TopTreeVertexData mapping_vertex(TopTreeClusterEffect f, TopTreeVertexData x){
return x;
}
static TopTreeClusterEffect composition(TopTreeClusterEffect l, TopTreeClusterEffect r){
return { l };
}
void reverse(){}
};
int main() {
int N; std::cin >> N;
using TopTreeInst = TopTree<TopTreeVertexData, TopTreeClusterData, TopTreeClusterEffect>;
std::vector<TopTreeInst::UnderlyingTreeVertex> A(N);
for(int i=0; i<N; i++){
A[i].data.has_on = false;
}
TopTreeInst top_tree;
for(int i=0; i<N-1; i++){
int u,v,w; std::cin >> u >> v >> w;
top_tree.link(&A[u], &A[v], TopTreeClusterData::edge(w));
}
int Q; std::cin >> Q;
for(int i=0; i<Q; i++){
int t; std::cin >> t;
if(t == 1){
int u,v,w,x; std::cin >> u >> v >> w >> x;
top_tree.cut(&A[u], &A[v], nullptr);
top_tree.link(&A[v], &A[w], TopTreeClusterData::edge(x));
}
if(t == 2){
int k; std::cin >> k;
if(k == 1) continue;
std::vector<int> X(k);
for(int i=0; i<k; i++){ std::cin >> X[i]; }
for(auto x : X){
top_tree.expose(&A[x]);
A[x].data.has_on = true;
}
auto c = top_tree.expose(&A[0]);
u64 ans = c->data.on;
auto l_on = c->boundary_left->data.has_on;
auto r_on = c->boundary_right->data.has_on;
if(l_on && r_on) ans += c->data.on_if_landr;
if(l_on) ans += c->data.on_if_l;
if(r_on) ans += c->data.on_if_r;
if(l_on || r_on) ans += c->data.on_if_lorr;
std::cout << ans << "\n";
for(auto x : X){
top_tree.expose(&A[x]);
A[x].data.has_on = false;
}
}
}
return 0;
}