結果

問題 No.1787 Do Use Dynamic Tree
ユーザー 👑 NachiaNachia
提出日時 2022-09-17 01:03:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,822 ms / 10,000 ms
コード長 28,993 bytes
コンパイル時間 924 ms
コンパイル使用メモリ 87,560 KB
実行使用メモリ 56,448 KB
最終ジャッジ日時 2024-12-21 23:55:07
合計ジャッジ時間 41,441 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 8 ms
5,248 KB
testcase_13 AC 8 ms
5,248 KB
testcase_14 AC 10 ms
5,248 KB
testcase_15 AC 8 ms
5,248 KB
testcase_16 AC 9 ms
5,248 KB
testcase_17 AC 10 ms
5,248 KB
testcase_18 AC 8 ms
5,248 KB
testcase_19 AC 8 ms
5,248 KB
testcase_20 AC 7 ms
5,248 KB
testcase_21 AC 10 ms
5,248 KB
testcase_22 AC 1,971 ms
33,152 KB
testcase_23 AC 1,607 ms
46,268 KB
testcase_24 AC 1,601 ms
28,800 KB
testcase_25 AC 2,605 ms
49,684 KB
testcase_26 AC 2,561 ms
49,656 KB
testcase_27 AC 2,603 ms
49,752 KB
testcase_28 AC 1,668 ms
56,448 KB
testcase_29 AC 1,635 ms
56,320 KB
testcase_30 AC 1,679 ms
56,448 KB
testcase_31 AC 2,234 ms
56,320 KB
testcase_32 AC 2,541 ms
56,368 KB
testcase_33 AC 2,822 ms
56,064 KB
testcase_34 AC 1,354 ms
56,320 KB
testcase_35 AC 2,147 ms
56,420 KB
testcase_36 AC 2,728 ms
56,072 KB
testcase_37 AC 2,084 ms
48,512 KB
testcase_38 AC 2,039 ms
48,384 KB
testcase_39 AC 2,012 ms
48,400 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#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[2] = { nullptr, 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]);
            bottomup_update();
        }
        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[0] = nullptr;
    boundary[1] = 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[0], boundary[1]);
    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[0]->data = TopTreeClusterEffect::mapping_vertex(f, mid_child->boundary[0]->data);
        }
        child[0]->boundary[1]->data = TopTreeClusterEffect::mapping_vertex(f, child[0]->boundary[1]->data);
    }
    if(node_type == NODE_TYPE_RAKE){
        for(int t : {0,1}) child[t]->apply_lazy_data(f);
        child[1]->boundary[0]->data = TopTreeClusterEffect::mapping_vertex(f, child[1]->boundary[0]->data);
    }
    lazy_data = TopTreeClusterEffect::id();
}
void TopTreeNode::bottomup_update(){
    if(node_type == NODE_TYPE_COMPRESS){
        auto cent = child[0]->boundary[1];
        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[0]->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[0]->data);
    }
}

void TopTreeNode::bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){
    node_type = NODE_TYPE_EDGE;
    child[0] = nullptr;
    child[1] = nullptr;
    mid_child = nullptr;
    boundary[0] = l;
    boundary[1] = 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[0]->handle = l;
    if(r->node_type != NODE_TYPE_RAKE) r->boundary[0]->handle = r;
    if (!special_for_hard_expose) {
        node_type = NODE_TYPE_RAKE;
        for(int t : {0,1}) boundary[t] = l->boundary[t];
        child[0] = l;
        l->parent = this;
        mid_child = nullptr;
        child[1] = r;
        r->parent = this;
        bottomup_update();
    }
    else {
        node_type = NODE_TYPE_RAKE;
        for(int t : {0,1}) boundary[t] = l->boundary[t];
        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[0]->data);
        buf.reverse();
        data = buf;
    }
}
void TopTreeNode::bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r){
    UnderlyingTreeVertex* bound = l->boundary[1];
    node_type = NODE_TYPE_COMPRESS;
    boundary[0] = l->boundary[0];
    boundary[1] = r->boundary[1];
    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[0]->handle = mid_child;

    bound->handle = this;
    for(int t : {0,1}) boundary[t]->handle = this;
}

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);
    p->bottomup_update();
    bottomup_compress(p, c_rake, c6);
}
void TopTreeNode::rotate_compress_right(){
    auto p = parent;
    
    std::swap(p->data, data);
    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);
    p->bottomup_update();
    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]);
        p->bottomup_update();
    }
    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);
        p->bottomup_update();
    }
}
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[0] == r || n_r->boundary[1] == 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[0] == target) n_target->reverse_boundary_vertices();
    if(n_target->boundary[1] == 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]);
    n_target->bottomup_update();
    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);
    to->bottomup_update();
}

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;
    for(int t : {0,1}) if(l->handle->boundary[t] != l) r = l->handle->boundary[t];

    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[0] == l && n_r->boundary[1] == r){
            // case (3) (4)
            // do nothing
        }
        else if(n_r->boundary[0] == l){
            // case (1)
            hard_expose_rake_case1(n_r);
        }
        else if(n_r->boundary[1] == 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);
                c->bottomup_update();
            }
            else{
                // case (2)
                c->mid_child->reverse_boundary_vertices();
                c->bottomup_compress(c->child[0], nullptr, c->mid_child);
                c->bottomup_update();
            }
        }
        else{
            // case (1)
            auto cc = c->child[0];
            cc->parent = nullptr;
            delete(c);
            c = cc;
            c->boundary[0]->handle = c;
            c->boundary[1]->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[0] == l && n_r->boundary[1] == r){
        // case (3)
        return false;
    }
    if(n_r->boundary[0] == l){
        // case (1)
        n_r->reverse_boundary_vertices();
        std::swap(l, r);
        // reduce to case (2)
    }
    if(n_r->boundary[1] == 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[0] == c){
            n_c->reverse_boundary_vertices();
        }
        if(n_c->boundary[1] == 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);
        n_l->bottomup_update();
        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_r->bottomup_update();
    n_l->bottomup_compress(n_l->child[0], n_l->mid_child, n_r);
    n_l->bottomup_update();
    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;
}
0