結果

問題 No.2296 Union Path Query (Hard)
ユーザー 👑 NachiaNachia
提出日時 2023-05-06 00:17:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,219 ms / 7,000 ms
コード長 30,682 bytes
コンパイル時間 1,607 ms
コンパイル使用メモリ 94,196 KB
最終ジャッジ日時 2025-02-12 20:17:39
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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] = {};
};
#include <vector>
#include <algorithm>
namespace nachia {
struct Dsu{
private:
int N;
std::vector<int> P;
std::vector<int> H;
public:
Dsu() : N(0) {}
Dsu(int n) : N(n), P(n, -1), H(n) {
for(int i=0; i<n; i++) H[i] = i;
}
int leader(int u){
if(P[u] < 0) return u;
int v = P[u];
while(P[v] >= 0){ P[u] = P[v]; u = v; v = P[v]; }
return P[u];
}
int append(){
int n = P.size();
P.push_back(-1);
H.push_back(n);
return n;
}
int label(int u){ return H[leader(u)]; }
int operator[](int u){ return H[leader(u)]; }
void merge(int u, int v, int newLabel){
if(newLabel < 0) newLabel = u;
u = leader(u);
v = leader(v);
if(u == v){ H[u] = newLabel; return; }
N--;
if(-P[u] < -P[v]) std::swap(u, v);
P[u] += P[v];
H[P[v] = u] = newLabel;
}
int merge(int u, int v){ merge(u, v, u); return u; }
int count(){ return N; }
int size(int u){ return -P[leader(u)]; }
bool same(int u, int v){ return leader(u) == leader(v); }
};
} // namespace nachia
struct TopTreeVertexData{
static TopTreeVertexData init(){ return {}; }
};
struct TopTreeClusterData{
long long l, r, len, diam;
static TopTreeClusterData edge(long long w){
return { w, w, w, w };
}
static TopTreeClusterData init(){ return { 0,0,0,0 }; }
static TopTreeClusterData compress(TopTreeClusterData l, TopTreeVertexData, TopTreeClusterData r){
return {
std::max(l.l, l.len + r.l),
std::max(r.r, r.len + l.r),
l.len + r.len,
std::max(std::max(l.diam, r.diam), l.r + r.l)
};
}
static TopTreeClusterData rake(TopTreeClusterData l, TopTreeClusterData r, TopTreeVertexData){
return {
std::max(l.l, l.len + r.r),
std::max(l.r, r.r),
l.len,
std::max(std::max(l.diam, r.diam), l.r + r.r)
};
}
void reverse(){
std::swap(l, 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(){}
};
#include <iostream>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N, X, Q; cin >> N >> X >> Q;
using TopTreeInst = TopTree<TopTreeVertexData, TopTreeClusterData, TopTreeClusterEffect>;
TopTreeInst toptree;
vector<TopTreeInst::UnderlyingTreeVertex> vtxs(N);
auto dsu = nachia::Dsu(N);
rep(i,Q){
int t; cin >> t;
if(t == 1){
int v, w; cin >> v >> w;
toptree.link(&vtxs[X], &vtxs[v], TopTreeClusterData::edge(w));
dsu.merge(v, X);
}
if(t == 2){
int u, v; cin >> u >> v;
if(!dsu.same(u, v)){
cout << "-1\n";
}
else if(u == v){
cout << 0 << '\n';
}
else{
long long x = toptree.expose(&vtxs[u], &vtxs[v])->data.len;
X = (X + x) % N;
cout << x << '\n';
}
}
if(t == 3){
int v; cin >> v;
if(dsu.size(v) == 1){
cout << "0\n";
}
else{
auto c = toptree.expose(&vtxs[v]);
cout << c->data.diam << '\n';
}
}
if(t == 4){
long long v; cin >> v;
X = (X + v) % N;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0