結果
| 問題 | No.902 Query ζone |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2022-12-25 20:08:08 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,140 ms / 5,000 ms |
| コード長 | 36,444 bytes |
| コンパイル時間 | 1,702 ms |
| コンパイル使用メモリ | 94,800 KB |
| 実行使用メモリ | 30,080 KB |
| 最終ジャッジ日時 | 2024-11-19 10:39:51 |
| 合計ジャッジ時間 | 18,692 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | 6 ms
5,248 KB |
| testcase_06 | AC | 1,093 ms
29,952 KB |
| testcase_07 | AC | 1,060 ms
30,080 KB |
| testcase_08 | AC | 1,060 ms
30,080 KB |
| testcase_09 | AC | 1,046 ms
30,080 KB |
| testcase_10 | AC | 1,054 ms
29,952 KB |
| testcase_11 | AC | 1,061 ms
30,080 KB |
| testcase_12 | AC | 1,064 ms
29,952 KB |
| testcase_13 | AC | 1,121 ms
30,080 KB |
| testcase_14 | AC | 1,117 ms
29,824 KB |
| testcase_15 | AC | 1,139 ms
30,080 KB |
| testcase_16 | AC | 1,140 ms
29,952 KB |
| testcase_17 | AC | 1,135 ms
29,952 KB |
| testcase_18 | AC | 1,108 ms
29,952 KB |
| testcase_19 | AC | 1,092 ms
30,080 KB |
ソースコード
#line 1 "Main.cpp"
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>
#include <string>
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() noexcept {
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() noexcept {
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) noexcept {
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) noexcept {
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() noexcept {
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() noexcept {
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() noexcept {
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() noexcept {
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() noexcept {
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() noexcept {
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() noexcept {
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) noexcept {
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] = {};
};
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;
bool has_on(){ return on_if_l || on_if_r || on; }
static TopTreeClusterData edge(u64 w){
TopTreeClusterData res;
res.on_if_landr = w;
res.on_if_l = res.on_if_r = res.on = 0;
return res;
}
static TopTreeClusterData init(){ return { 0,0,0,0 }; }
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();
(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;
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;
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();
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;
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;
}
else{
u64 res_on_if_lorr = 0;
(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;
res.on += r.on;
res.on_if_l += res_on_if_lorr; res.on_if_r += res_on_if_lorr; res.on_if_landr -= res_on_if_lorr;
}
return res;
}
void reverse(){
std::swap(on_if_l, on_if_r);
}
};
struct TopTreeClusterEffect{
static TopTreeClusterEffect id(){ return { }; }
static TopTreeClusterData mapping_cluster(TopTreeClusterEffect, TopTreeClusterData x){
return x;
}
static TopTreeVertexData mapping_vertex(TopTreeClusterEffect, TopTreeVertexData x){
return x;
}
static TopTreeClusterEffect composition(TopTreeClusterEffect l, TopTreeClusterEffect){
return { l };
}
void reverse(){}
};
#line 2 "nachia\\misc\\fastio.hpp"
#include <cstdio>
#include <cctype>
#include <cstdint>
#line 6 "nachia\\misc\\fastio.hpp"
namespace nachia{
struct CInStream{
private:
static const unsigned int INPUT_BUF_SIZE = 1 << 17;
unsigned int p = INPUT_BUF_SIZE;
static char Q[INPUT_BUF_SIZE];
public:
using MyType = CInStream;
char seekChar() noexcept {
if(p == INPUT_BUF_SIZE){
size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);
if(len != INPUT_BUF_SIZE) Q[len] = '\0';
p = 0;
}
return Q[p];
}
void skipSpace() noexcept { while(isspace(seekChar())) p++; }
uint32_t nextU32() noexcept {
skipSpace();
uint32_t buf = 0;
while(true){
char tmp = seekChar();
if('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
int32_t nextI32() noexcept {
skipSpace();
if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); }
return (int32_t)nextU32();
}
uint64_t nextU64() noexcept {
skipSpace();
uint64_t buf = 0;
while(true){
char tmp = seekChar();
if('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
int64_t nextI64() noexcept {
skipSpace();
if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); }
return (int64_t)nextU64();
}
char nextChar() noexcept { skipSpace(); char buf = seekChar(); p++; return buf; }
std::string nextToken(){
skipSpace();
std::string buf;
while(true){
char ch = seekChar();
if(isspace(ch) || ch == '\0') break;
buf.push_back(ch);
p++;
}
return buf;
}
MyType& operator>>(unsigned int& dest) noexcept { dest = nextU32(); return *this; }
MyType& operator>>(int& dest) noexcept { dest = nextI32(); return *this; }
MyType& operator>>(unsigned long& dest) noexcept { dest = nextU64(); return *this; }
MyType& operator>>(long& dest) noexcept { dest = nextI64(); return *this; }
MyType& operator>>(unsigned long long& dest) noexcept { dest = nextU64(); return *this; }
MyType& operator>>(long long& dest) noexcept { dest = nextI64(); return *this; }
MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; }
MyType& operator>>(char& dest) noexcept { dest = nextChar(); return *this; }
} cin;
struct FastOutputTable{
char LZ[1000][4] = {};
char NLZ[1000][4] = {};
constexpr FastOutputTable(){
using u32 = uint_fast32_t;
for(u32 d=0; d<1000; d++){
LZ[d][0] = ('0' + d / 100 % 10);
LZ[d][1] = ('0' + d / 10 % 10);
LZ[d][2] = ('0' + d / 1 % 10);
LZ[d][3] = '\0';
}
for(u32 d=0; d<1000; d++){
u32 i = 0;
if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);
if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10);
if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10);
NLZ[d][i++] = '\0';
}
}
};
struct COutStream{
private:
using u32 = uint32_t;
using u64 = uint64_t;
using MyType = COutStream;
static const u32 OUTPUT_BUF_SIZE = 1 << 17;
static char Q[OUTPUT_BUF_SIZE];
static constexpr FastOutputTable TB = FastOutputTable();
u32 p = 0;
static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; }
static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; }
template<class T, class U> static void Fil(T& m, U& l, U x) noexcept { m = l/x; l -= m*x; }
void next_dig9(u32 x){
u32 y;
Fil(y, x, P10(6));
nextCstr(TB.LZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
}
public:
void nextChar(char c){
Q[p++] = c;
if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; }
}
void nextEoln(){ nextChar('\n'); }
void nextCstr(const char* s){ while(*s) nextChar(*(s++)); }
void nextU32(uint32_t x){
u32 y = 0;
if(x >= P10(9)){
Fil(y, x, P10(9));
nextCstr(TB.NLZ[y]); next_dig9(x);
}
else if(x >= P10(6)){
Fil(y, x, P10(6));
nextCstr(TB.NLZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
}
else if(x >= P10(3)){
Fil(y, x, P10(3));
nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]);
}
else if(x >= 1) nextCstr(TB.NLZ[x]);
else nextChar('0');
}
void nextI32(int32_t x){
if(x >= 0) nextU32(x);
else{ nextChar('-'); nextU32((u32)-x); }
}
void nextU64(uint64_t x){
u32 y = 0;
if(x >= P10L(18)){
Fil(y, x, P10L(18));
nextU32(y);
Fil(y, x, P10L(9));
next_dig9(y); next_dig9(x);
}
else if(x >= P10L(9)){
Fil(y, x, P10L(9));
nextU32(y); next_dig9(x);
}
else nextU32(x);
}
void nextI64(int64_t x){
if(x >= 0) nextU64(x);
else{ nextChar('-'); nextU64((u64)-x); }
}
void writeToFile(bool flush = false){
fwrite(Q, p, 1, stdout);
if(flush) fflush(stdout);
p = 0;
}
COutStream(){ Q[0] = 0; }
~COutStream(){ writeToFile(); }
MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; }
MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; }
MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; }
MyType& operator<<(int tg){ nextI32(tg); return *this; }
MyType& operator<<(long tg){ nextI64(tg); return *this; }
MyType& operator<<(long long tg){ nextI64(tg); return *this; }
MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; }
MyType& operator<<(const char* tg){ nextCstr(tg); return *this; }
MyType& operator<<(char tg){ nextChar(tg); return *this; }
} cout;
char CInStream::Q[INPUT_BUF_SIZE];
char COutStream::Q[OUTPUT_BUF_SIZE];
} // namespace nachia
#line 794 "Main.cpp"
int main() {
using nachia::cin, nachia::cout;
int N; 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; cin >> u >> v >> w;
top_tree.link(&A[u], &A[v], TopTreeClusterData::edge(w));
}
int Q; cin >> Q;
for(int i=0; i<Q; i++){
int t; cin >> t;
if(t == 1){
int u,v,w,x; 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; cin >> k;
if(k == 1) continue;
std::vector<int> X(k);
for(int i=0; i<k; i++){ 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;
cout << ans << "\n";
for(auto x : X){
top_tree.expose(&A[x]);
A[x].data.has_on = false;
}
}
}
return 0;
}