#825583 (C++17) No.2163 LCA Sum Query

提出ソース
結果

問題	No.2163 LCA Sum Query
ユーザー	👑 Nachia
提出日時	2022-12-14 02:55:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,642 ms / 6,000 ms
コード長	28,861 bytes
コンパイル時間	1,044 ms
コンパイル使用メモリ	88,780 KB
実行使用メモリ	36,096 KB
最終ジャッジ日時	2024-04-27 04:23:54
合計ジャッジ時間	37,086 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	3 ms 6,944 KB
testcase_03	AC	4 ms 6,940 KB
testcase_04	AC	4 ms 6,940 KB
testcase_05	AC	4 ms 6,944 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	3 ms 6,944 KB
testcase_08	AC	4 ms 6,940 KB
testcase_09	AC	4 ms 6,944 KB
testcase_10	AC	6 ms 6,940 KB
testcase_11	AC	4 ms 6,944 KB
testcase_12	AC	632 ms 6,944 KB
testcase_13	AC	1,642 ms 25,856 KB
testcase_14	AC	1,093 ms 29,824 KB
testcase_15	AC	251 ms 6,940 KB
testcase_16	AC	755 ms 26,368 KB
testcase_17	AC	685 ms 14,464 KB
testcase_18	AC	401 ms 6,944 KB
testcase_19	AC	280 ms 6,940 KB
testcase_20	AC	124 ms 15,744 KB
testcase_21	AC	344 ms 14,976 KB
testcase_22	AC	1,309 ms 31,360 KB
testcase_23	AC	1,633 ms 31,360 KB
testcase_24	AC	1,288 ms 31,360 KB
testcase_25	AC	1,618 ms 31,360 KB
testcase_26	AC	1,217 ms 32,128 KB
testcase_27	AC	1,527 ms 32,128 KB
testcase_28	AC	1,192 ms 32,128 KB
testcase_29	AC	1,541 ms 32,128 KB
testcase_30	AC	1,167 ms 28,416 KB
testcase_31	AC	1,548 ms 28,288 KB
testcase_32	AC	1,141 ms 28,288 KB
testcase_33	AC	1,489 ms 28,160 KB
testcase_34	AC	1,134 ms 36,096 KB
testcase_35	AC	1,552 ms 36,096 KB
testcase_36	AC	1,100 ms 36,096 KB
testcase_37	AC	1,528 ms 35,968 KB
testcase_38	AC	1,049 ms 32,128 KB
testcase_39	AC	1,361 ms 32,128 KB
testcase_40	AC	1,285 ms 32,128 KB
testcase_41	AC	1,381 ms 32,128 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>
#include <string>



#include <iostream>



struct TopTreeVertexData{
    int z;
    int n;
    static TopTreeVertexData e(){ return {0, 0}; }
};
struct TopTreeClusterData{
    using i64 = long long;
    i64 corner_n[2] = {};
    i64 corner_nn[2] = {};
    i64 corner_nnz[2] = {};
    i64 mid_n = {};
    i64 mid_nz[2] = {};
    i64 mid_nnz[2] = {};
    static TopTreeClusterData e(){ return TopTreeClusterData(); }
    i64 size_n() const noexcept { return corner_n[0] + corner_n[1] + mid_n; }
    static TopTreeClusterData compress(TopTreeClusterData l, TopTreeVertexData mid, TopTreeClusterData r){
        i64 mid_vertex_n = l.corner_n[1] + r.corner_n[0] + mid.n;
        i64 mid_vertex_nn = l.corner_nn[1] + r.corner_nn[0] + mid.n * (l.corner_n[1] + r.corner_n[0]) + l.corner_n[1] * r.corner_n[0];
        i64 rsize = r.size_n();
        TopTreeClusterData res;
        res.corner_n[0] = l.corner_n[0];
        res.corner_n[1] = r.corner_n[1];
        res.corner_nn[0] = l.corner_nn[0];
        res.corner_nn[1] = r.corner_nn[1];
        res.corner_nnz[0] = l.corner_nnz[0];
        res.corner_nnz[1] = r.corner_nnz[1];
        res.mid_n = l.mid_n + r.mid_n + mid_vertex_n;
        res.mid_nz[0] = l.mid_nz[0] + r.mid_nz[0] + mid_vertex_n * mid.z;
        res.mid_nz[1] = l.mid_nz[1] + r.mid_nz[1] + mid_vertex_n * mid.z;
        res.mid_nnz[0] = l.mid_nnz[0] + r.mid_nnz[0] + l.corner_nnz[1] + r.corner_nnz[0]
            + l.mid_nz[0] * (mid_vertex_n + r.mid_n + r.corner_n[1])
            + mid.z * mid_vertex_nn
            + mid.z * mid_vertex_n * (r.mid_n + r.corner_n[1]);
        res.mid_nnz[1] = l.mid_nnz[1] + r.mid_nnz[1] + l.corner_nnz[1] + r.corner_nnz[0]
            + r.mid_nz[1] * (mid_vertex_n + l.mid_n + l.corner_n[0])
            + mid.z * mid_vertex_nn
            + mid.z * mid_vertex_n * (l.mid_n + l.corner_n[0]);
        return res;
    }
    static TopTreeClusterData rake(TopTreeClusterData l, TopTreeClusterData r, TopTreeVertexData r_end){
        i64 rsize = r.size_n();
        TopTreeClusterData res;
        res.corner_n[0] = l.corner_n[0];
        res.corner_n[1] = l.corner_n[1] + rsize + r_end.n;
        res.corner_nn[0] = l.corner_nn[0];
        res.corner_nn[1] = l.corner_nn[1] + r.corner_nn[1]
            + l.corner_n[1] * (rsize + r_end.n)
            + r.corner_n[1] * (r.mid_n + r.corner_n[0] + r_end.n);
        res.corner_nnz[0] = l.corner_nnz[0];
        res.corner_nnz[1] = l.corner_nnz[1] + r.corner_nnz[1] + r.mid_nnz[1] + r.corner_nnz[0]
            + (r.corner_nn[0] + r_end.n * r.corner_n[0]) * r_end.z
            + r.mid_nz[1] * (r_end.n + r.corner_n[0]);
        res.mid_n = l.mid_n;
        res.mid_nz[0] = l.mid_nz[0];
        res.mid_nz[1] = l.mid_nz[1];
        res.mid_nnz[0] = l.mid_nnz[0];
        res.mid_nnz[1] = l.mid_nnz[1];
        return res;
    }
    void reverse(){
        std::swap(corner_n[0], corner_n[1]);
        std::swap(corner_nn[0], corner_nn[1]);
        std::swap(corner_nnz[0], corner_nnz[1]);
        std::swap(mid_nz[0], mid_nz[1]);
        std::swap(mid_nnz[0], mid_nnz[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]);
        }
        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;
    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[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]);
    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;
    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);
            }
            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[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);
        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;
}


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;



int main(){
    int N, Q; cin >> N >> Q;
    vector<UnderlyingTreeVertex> vtxs(N*2);
    rep(i,N) vtxs[i].data.n = 0;
    rep(i,N) vtxs[i].data.z = i+1;
    TopTree toptree;
    rep(i,N-1){
        int u,v; cin >> u >> v; u--; v--;
        toptree.link(&vtxs[u], &vtxs[v]);
    }
    rep(i,N) toptree.link(&vtxs[i], &vtxs[i+N]);

    rep(i,Q){
        int u,r,v; cin >> u >> r >> v; u--; r--; v--;
        toptree.expose(&vtxs[u]);
        vtxs[u].data.n ^= 1;
        auto data = toptree.expose(&vtxs[r+N], &vtxs[v])->data;
        i64 ans = data.corner_nnz[1] + data.corner_nn[1] * vtxs[v].data.z + data.corner_n[1] * vtxs[v].data.n * vtxs[v].data.z;
        cout << ans << '\n';
    }
    return 0;
}



struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
yukicoder

結果

テストケース

ソースコード
