結果
| 問題 |
No.1787 Do Use Dynamic Tree
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2022-09-16 23:53:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3,532 ms / 10,000 ms |
| コード長 | 28,888 bytes |
| コンパイル時間 | 1,081 ms |
| コンパイル使用メモリ | 85,940 KB |
| 最終ジャッジ日時 | 2025-02-07 10:49:18 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 38 |
ソースコード
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>
#include <string>
#include <iostream>
struct TopTreeVertexData{
int x;
int index;
static TopTreeVertexData e(){ return { -1, -1 }; }
};
struct TopTreeClusterData{
int raked[2] = {-1,-1};
int rake_ans[2] = {-1,-1};
int ans[2] = {-1,-1};
int nx_rake[2] = {-1,-1};
int nx_rake_ans[2] = {-1,-1};
int nx[2] = {-1,-1};
static TopTreeClusterData e(){ return TopTreeClusterData(); }
static TopTreeClusterData compress(TopTreeClusterData l, TopTreeVertexData mid, TopTreeClusterData r){
int mid_rake = std::max(l.raked[1], r.raked[0]);
int mid_rake_ans = (mid_rake == l.raked[1]) ? l.rake_ans[1] : r.rake_ans[0];
TopTreeClusterData res;
for(int t=0; t<2; t++){
res.raked[t] = l.raked[t];
res.rake_ans[t] = l.rake_ans[t];
if(l.ans[t] != -1) res.ans[t] = l.ans[t];
else if(mid.x < l.nx_rake[t^1]) res.ans[t] = l.nx_rake_ans[t^1];
else if(r.nx[t] == -1) res.ans[t] = -1;
else if(r.nx[t] < mid_rake) res.ans[t] = mid_rake_ans;
else res.ans[t] = r.ans[t];
if(l.nx[t] == -1){
res.nx_rake[t] = mid_rake;
res.nx_rake_ans[t] = mid_rake_ans;
res.nx[t] = mid.x;
}
else{
res.nx_rake[t] = l.nx_rake[t];
res.nx_rake_ans[t] = l.nx_rake_ans[t];
res.nx[t] = l.nx[t];
}
std::swap(l,r);
}
return res;
}
int query(TopTreeVertexData tg){
int nx_ex = (nx[1] == -1) ? tg.x : nx[1];
if(nx_ex < raked[1]) return rake_ans[1];
if(ans[1] != -1) return ans[1];
if(tg.x < nx_rake[0]) return nx_rake_ans[0];
if(raked[0] == -1) return tg.index;
return rake_ans[0];
}
static TopTreeClusterData rake(TopTreeClusterData l, TopTreeClusterData r, TopTreeVertexData r_end){
int mid_rake = std::max({ l.raked[1], r.raked[1], r.nx[1] });
int mid_rake_ans = -1;
if(mid_rake == r.raked[1]) mid_rake_ans = r.rake_ans[1];
else if(mid_rake == r.nx[1]){
if(r.ans[1] != -1) mid_rake_ans = r.ans[1];
else if(r_end.x < r.nx_rake[0]) mid_rake_ans = r.nx_rake_ans[0];
else if(r.raked[0] == -1) mid_rake_ans = r_end.index;
else mid_rake_ans = r.rake_ans[0];
}
else if(mid_rake == l.raked[1]) mid_rake_ans = l.rake_ans[1];
if(r.nx[1] == -1 && mid_rake < r_end.x){ mid_rake = r_end.x; mid_rake_ans = r_end.index; }
TopTreeClusterData res;
res.raked[0] = l.raked[0];
res.rake_ans[0] = l.rake_ans[0];
res.raked[1] = mid_rake;
res.rake_ans[1] = mid_rake_ans;
res.ans[0] = l.ans[0];
res.ans[1] = l.ans[1];
res.nx_rake[0] = l.nx_rake[0];
res.nx_rake_ans[0] = l.nx_rake_ans[0];
res.nx_rake[1] = l.nx_rake[1];
res.nx_rake_ans[1] = l.nx_rake_ans[1];
res.nx[0] = l.nx[0];
res.nx[1] = l.nx[1];
return res;
}
void reverse(){
std::swap(raked[0], raked[1]);
std::swap(rake_ans[0], rake_ans[1]);
std::swap(ans[0], ans[1]);
std::swap(nx_rake[0], nx_rake[1]);
std::swap(nx_rake_ans[0], nx_rake_ans[1]);
std::swap(nx[0], nx[1]);
}
};
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 {}; }
};
struct TopTreeNode;
struct UnderlyingTreeVertex;
struct TopTree;
struct TopTreeNode{
public:
TopTreeNode* parent = nullptr;
TopTreeNode* child[2] = { nullptr, 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::e();
TopTreeClusterEffect lazy_data = TopTreeClusterEffect::id();
void get_propagated();
private:
void disable();
TopTreeNode*& parentchild();
public:
void block(){
for(int t : {0,1}) if(child[t]) child[t]->parent = nullptr;
if(mid_child) mid_child->parent = nullptr;
}
void unblock(TopTreeNode* new_root){
for(int t : {0,1}) if (child[t] && !child[t]->is_root()) child[t] = new_root;
if(mid_child && !mid_child->is_root()) mid_child = new_root;
if(node_type == NODE_TYPE_COMPRESS){
bottomup_compress(child[0], mid_child, child[1]);
}
if(node_type == NODE_TYPE_RAKE){
bottomup_rake(child[0], child[1]);
}
}
void reverse_boundary_vertices();
void apply_lazy_data(TopTreeClusterEffect f);
void lazy_propagation();
void bottomup_update();
void bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r);
void bottomup_rake(TopTreeNode* l, TopTreeNode* r, bool special_for_hard_expose = false);
void bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r);
void rotate_rake_left();
void rotate_rake_right();
void rotate_compress_left();
void rotate_compress_right();
void splay_soft_rake();
void splay_rake();
void splay_compress();
void splice(bool hard_expose_rake_to_left = true);
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::e();
}
void exposing_target(bool e = false);
bool exposing_source(UnderlyingTreeVertex* target);
};
struct TopTree{
private:
void soft_expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r);
void undo_hard_expose();
public:
TopTreeNode* expose(UnderlyingTreeVertex* l);
TopTreeNode* expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, bool do_hard = true);
bool cut(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r);
bool link(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r);
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*);
void execute();
};
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] = {};
};
void TopTreeNode::disable(){
node_type = NODE_TYPE_DISABLED;
parent = nullptr;
child[0] = nullptr;
child[1] = nullptr;
mid_child = nullptr;
boundary_left = nullptr;
boundary_right = nullptr;
bouundary_vertices_are_reversed = false;
}
TopTreeNode*& TopTreeNode::parentchild(){
TopTreeNode* p = parent;
for(int t : {0,1}) if(p->child[t] == this) return p->child[t];
if(p->mid_child == this) return p->mid_child;
exit(1);
}
void TopTreeNode::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(child[0], child[1]);
}
}
void TopTreeNode::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;
}
}
void TopTreeNode::apply_lazy_data(TopTreeClusterEffect f){
lazy_data = TopTreeClusterEffect::composition(f, lazy_data);
data = TopTreeClusterEffect::mapping_cluster(f, data);
}
void TopTreeNode::lazy_propagation(){
if(bouundary_vertices_are_reversed){
if(node_type == NODE_TYPE_COMPRESS){
for(int t : {0,1}) child[t]->reverse_boundary_vertices();
}
}
bouundary_vertices_are_reversed = false;
auto f = lazy_data;
if(node_type == NODE_TYPE_COMPRESS){
for(int t : {0,1}) child[t]->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);
}
child[0]->boundary_right->data = TopTreeClusterEffect::mapping_vertex(f, child[0]->boundary_right->data);
}
if(node_type == NODE_TYPE_RAKE){
for(int t : {0,1}) child[t]->apply_lazy_data(f);
child[1]->boundary_left->data = TopTreeClusterEffect::mapping_vertex(f, child[1]->boundary_left->data);
}
lazy_data = TopTreeClusterEffect::id();
}
void TopTreeNode::bottomup_update(){
if(node_type == NODE_TYPE_COMPRESS){
auto cent = child[0]->boundary_right;
auto l_data = child[0]->data;
auto r_data = child[1]->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, r_data);
}
else if(node_type == NODE_TYPE_RAKE){
data = TopTreeClusterData::rake(child[0]->data, child[1]->data, child[1]->boundary_left->data);
}
}
void TopTreeNode::bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){
node_type = NODE_TYPE_EDGE;
child[0] = nullptr;
child[1] = nullptr;
mid_child = nullptr;
boundary_left = l;
boundary_right = r;
l->handle = this;
r->handle = this;
data = TopTreeClusterData::e();
lazy_data = TopTreeClusterEffect::id();
}
void TopTreeNode::bottomup_rake(TopTreeNode* l, TopTreeNode* r, bool special_for_hard_expose){
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;
child[0] = l;
l->parent = this;
mid_child = nullptr;
child[1] = r;
r->parent = this;
bottomup_update();
}
else {
node_type = NODE_TYPE_RAKE;
boundary_left = l->boundary_left;
boundary_right = l->boundary_right;
child[0] = l;
l->parent = this;
mid_child = nullptr;
child[1] = r;
r->parent = this;
auto buf = child[0]->data;
buf.reverse();
buf = TopTreeClusterData::rake(buf, child[1]->data, child[1]->boundary_left->data);
buf.reverse();
data = buf;
}
}
void TopTreeNode::bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r){
UnderlyingTreeVertex* bound = l->boundary_right;
node_type = NODE_TYPE_COMPRESS;
boundary_left = l->boundary_left;
boundary_right = r->boundary_right;
child[0] = l;
l->parent = this;
mid_child = m_rake;
if(m_rake) m_rake->parent = this;
child[1] = 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;
bottomup_update();
}
void TopTreeNode::rotate_rake_left(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto c0 = p->child[0];
auto c1 = child[0];
auto c2 = child[1];
p->bottomup_rake(c0, c1);
bottomup_rake(p, c2);
}
void TopTreeNode::rotate_rake_right(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto c0 = child[0];
auto c1 = child[1];
auto c2 = p->child[1];
p->bottomup_rake(c1, c2);
bottomup_rake(c0, p);
}
void TopTreeNode::rotate_compress_left(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto p_rake = p->mid_child;
auto c_rake = this->mid_child;
auto c1 = p->child[0];
auto c4 = this->child[0];
auto c6 = this->child[1];
p->bottomup_compress(c1, p_rake, c4);
bottomup_compress(p, c_rake, c6);
}
void TopTreeNode::rotate_compress_right(){
auto p = parent;
if(!p->is_root()) p->parentchild() = this;
parent = p->parent;
auto p_rake = p->mid_child;
auto c_rake = this->mid_child;
auto c1 = this->child[0];
auto c3 = this->child[1];
auto c6 = p->child[1];
p->bottomup_compress(c3, p_rake, c6);
bottomup_compress(c1, c_rake, p);
}
void TopTreeNode::splay_soft_rake(){
while(!is_rake_root()){
auto p = parent;
if(p->is_rake_root()){
if(p->child[0] == this){ rotate_rake_right(); }
else{ rotate_rake_left(); }
}
else{
auto pp = p->parent;
if(p->child[0] == this){
if(pp->child[0] == p){ p->rotate_rake_right(); rotate_rake_right(); }
else { rotate_rake_right(); rotate_rake_left(); }
}
else{
if(pp->child[1] == p){ p->rotate_rake_left(); rotate_rake_left(); }
else { rotate_rake_left(); rotate_rake_right(); }
}
}
}
}
void TopTreeNode::splay_rake(){
if(is_rake_root()) return;
auto p1 = parent;
p1->splay_soft_rake();
auto p2 = parent;
if(p2 == p1) return;
p1->block();
p2->splay_soft_rake();
p1->unblock(p2);
}
void TopTreeNode::splay_compress(){
while(!is_compress_root()){
auto p = parent;
if(p->is_compress_root()){
if(p->child[0] == this){ rotate_compress_right(); }
else{ rotate_compress_left(); }
}
else{
auto pp = p->parent;
if(p->child[0] == this){
if(pp->child[0] == p){ p->rotate_compress_right(); rotate_compress_right(); }
else { rotate_compress_right(); rotate_compress_left(); }
}
else{
if(pp->child[1] == p){ p->rotate_compress_left(); rotate_compress_left(); }
else { rotate_compress_left(); rotate_compress_right(); }
}
}
}
}
void TopTreeNode::splice(bool compress_on_left){
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->child[0] == this);
while(p->node_type == NODE_TYPE_RAKE){
if(is_this_left_child){
rake_r = p->child[1];
rake_rp = p;
}
else{
rake_l = p->child[0];
rake_lp = p;
}
auto pp = p->parent;
is_this_left_child = (pp->child[0] == p);
p = pp;
}
if(compress_on_left){
auto rake_r1 = p->child[0];
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->child[1]);
}
else{
reverse_boundary_vertices();
auto rake_r1 = p->child[1];
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->child[0], rake_r1, this);
}
}
void TopTree::soft_expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){
r->exposing_target(true);
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->child[1] == n_l) n_r->reverse_boundary_vertices();
n_r->lazy_propagation();
n_l->lazy_propagation();
}
}
void UnderlyingTreeVertex::exposing_target(bool e){
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;
c->get_propagated();
while(!c->is_root()){
c->splice();
c = c->parent;
}
handle->splay_compress();
}
bool UnderlyingTreeVertex::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
for(int t : {0,1}) n_target->child[t]->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;
}
for(int t : {0,1}) if (!n_target->child[t]->is_root()) n_target->child[t] = 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->child[1] == p->parent) compress_to_left = false;
c->splice(compress_to_left);
c = c->parent;
if(n_target == c){
for(int t : {0,1}) n_target->child[t]->parent = nullptr;
}
}
c = handle;
c->get_propagated();
c->splay_compress();
for(int t : {0,1}) if (!n_target->child[t]->is_root()) n_target->child[t] = c;
n_target->bottomup_compress(n_target->child[0], n_target->mid_child, n_target->child[1]);
if(c->is_root()) return false;
if(n_target->child[1] == c){
n_target->reverse_boundary_vertices();
n_target->lazy_propagation();
}
return true;
}
TopTree::HardExposeUndoUnit::HardExposeUndoUnit(TopTreeNode* v){
to = v;
l = v->child[0];
m_rake = v->mid_child;
r = v->child[1];
}
void TopTree::HardExposeUndoUnit::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);
}
void TopTree::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;
}
TopTreeNode* TopTree::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* TopTree::expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, bool do_hard){
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->child[1]->reverse_boundary_vertices();
TopTreeNode* rake_r = c->child[1];
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->child[0], 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->child[0];
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->child[1], 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 TopTree::cut(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){
if(!l){ std::cerr << "TopTree::link : l is null" << std::endl; exit(1); }
if(!r){ std::cerr << "TopTree::link : r is null" << std::endl; exit(1); }
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->child[0]->node_type == TopTreeNode::NODE_TYPE_RAKE){
most_left_rake = most_left_rake->child[0];
most_left_rake->lazy_propagation();
}
most_left_rake->splay_soft_rake();
most_left_rake = most_left_rake->child[0];
most_left_rake->reverse_boundary_vertices();
c->bottomup_compress(c->child[0], c->mid_child->child[1], most_left_rake);
}
else{
// case (2)
c->mid_child->reverse_boundary_vertices();
c->bottomup_compress(c->child[0], nullptr, c->mid_child);
}
}
else{
// case (1)
auto cc = c->child[0];
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;
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->child[1];
if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;
delete(lr);
n_r->child[1] = 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->child[1];
if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;
delete(lr);
n_r->child[0] = nullptr;
n_l->child[1] = nullptr;
n_l->parent = nullptr;
fix_tmporary_state(n_l);
n_r->child[0] = n_r->child[1];
n_r->child[0]->reverse_boundary_vertices();
fix_tmporary_state(n_r);
return true;
}
bool TopTree::link(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){
if(!l){ std::cerr << "TopTree::link : l is null" << std::endl; exit(1); }
if(!r){ std::cerr << "TopTree::link : r is null" << std::endl; exit(1); }
undo_hard_expose();
auto make_temporary_state = [this](UnderlyingTreeVertex* c)->TopTreeNode* {
if(!c){ std::cerr << "TopTree::link internal error 1" << std::endl; exit(1); }
if(!c->handle->is_root()){ std::cerr << "TopTree::link internal error 2 : not exposed" << std::endl; exit(1); }
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->child[0] = n_c;
return unstable_root;
}
// c is not a leaf
n_c->lazy_propagation();
auto r_rake = n_c->child[1];
n_c->child[1] = 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);
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);
n_l->bottomup_compress(n_l->child[0], 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->child[0], n_r->child[1]);
n_r->child[1]->reverse_boundary_vertices();
auto lr = new TopTreeNode();
lr->bottomup_edge(l, r);
n_r->bottomup_compress(lr, n_r->mid_child, n_r->child[1]);
n_l->bottomup_compress(n_l->child[0], n_l->mid_child, n_r);
return true;
}
using namespace std;
int main() {
int N; cin >> N;
vector<UnderlyingTreeVertex> A(N);
for(int i=0; i<N; i++){
A[i].data.x = i;
A[i].data.index = i;
}
TopTree top_tree;
for(int i=0; i<N-1; i++){
int u,v; cin >> u >> v; u--; v--;
top_tree.link(&A[u], &A[v]);
}
int Q; cin >> Q;
int preans = 0;
for(int i=0; i<Q; i++){
int u,v; cin >> u >> v; u--; v--;
u = (u + preans) % N;
v = (v + preans) % N;
auto c = top_tree.expose(&A[v], &A[u]);
swap(A[u].data.x, A[v].data.x);
int ans = c->data.query(A[v].data);
cout << (ans + 1) << "\n";
preans = ans + 1;
}
return 0;
}