結果
| 問題 |
No.2163 LCA Sum Query
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2022-12-14 02:55:17 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,794 ms / 6,000 ms |
| コード長 | 28,861 bytes |
| コンパイル時間 | 3,825 ms |
| コンパイル使用メモリ | 120,836 KB |
| 最終ジャッジ日時 | 2025-02-09 11:21:57 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 40 |
ソースコード
#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;