結果
問題 | No.2296 Union Path Query (Hard) |
ユーザー |
👑 ![]() |
提出日時 | 2023-05-06 00:17:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,219 ms / 7,000 ms |
コード長 | 30,682 bytes |
コンパイル時間 | 1,607 ms |
コンパイル使用メモリ | 94,196 KB |
最終ジャッジ日時 | 2025-02-12 20:17:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 45 |
ソースコード
#include <vector>#include <utility>#include <algorithm>#include <cassert>#include <string>#include <iostream>template<class TopTreeVertexData,class TopTreeClusterData,class TopTreeClusterEffect>struct TopTree{public:struct TopTreeNode;struct UnderlyingTreeVertex;private:void soft_expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r){r->exposing_target();auto n_l = l->handle;auto n_r = r->handle;if(n_l == n_r){if(n_r->boundary_left == r || n_r->boundary_right == l){n_r->reverse_boundary_vertices();n_r->lazy_propagation();}}else{l->exposing_source(r);n_r = r->handle;if(n_r->right_child == n_l) n_r->reverse_boundary_vertices();n_r->lazy_propagation();n_l->lazy_propagation();}}void undo_hard_expose(){for(int i=hard_expose_new_rakes_length-1; i>=0; i--){hard_expose_new_rakes[i].first->lazy_propagation();}for(int i=hard_expose_new_rakes_length-1; i>=0; i--){if(hard_expose_new_rakes[i].second) delete(hard_expose_new_rakes[i].first);}hard_expose_new_rakes_length = 0;for(int i=0; i<hard_expose_undo_length; i++){hard_expose_undo_memo[i].execute();}hard_expose_undo_length = 0;}public:struct TopTreeNode{public:TopTreeNode* parent = nullptr;TopTreeNode* right_child = nullptr;TopTreeNode* left_child = nullptr;TopTreeNode* mid_child = nullptr;UnderlyingTreeVertex* boundary_left = nullptr;UnderlyingTreeVertex* boundary_right = nullptr;bool bouundary_vertices_are_reversed = false;enum TopTreeNodeType { NODE_TYPE_DISABLED, NODE_TYPE_EDGE, NODE_TYPE_RAKE, NODE_TYPE_COMPRESS };TopTreeNodeType node_type = NODE_TYPE_DISABLED;TopTreeClusterData data = TopTreeClusterData::init();TopTreeClusterEffect lazy_data = TopTreeClusterEffect::id();void get_propagated(){TopTreeNode* pp = parent;TopTreeNode* p = this;TopTreeNode* tmp = nullptr;p->parent = nullptr;while(pp){tmp = pp->parent;pp->parent = p;p = pp;pp = tmp;}while(p){p->lazy_propagation();tmp = p->parent;p->parent = pp;pp = p;p = tmp;}}private:void disable(){node_type = NODE_TYPE_DISABLED;parent = nullptr;left_child = nullptr;right_child = nullptr;mid_child = nullptr;boundary_left = nullptr;boundary_right = nullptr;bouundary_vertices_are_reversed = false;}TopTreeNode*& parentchild(){TopTreeNode* p = parent;if(p->left_child == this) return p->left_child;if(p->right_child == this) return p->right_child;if(p->mid_child == this) return p->mid_child;exit(1);}public:void block(){if(left_child) left_child->parent = nullptr;if(right_child) right_child->parent = nullptr;if(mid_child) mid_child->parent = nullptr;}void unblock(TopTreeNode* new_root){if (left_child && !left_child->is_root()) left_child = new_root;if (right_child && !right_child->is_root()) right_child = new_root;if (mid_child && !mid_child->is_root()) mid_child = new_root;if(node_type == NODE_TYPE_COMPRESS){bottomup_compress(left_child, mid_child, right_child);}if(node_type == NODE_TYPE_RAKE){bottomup_rake(left_child, right_child);}}void reverse_boundary_vertices(){bouundary_vertices_are_reversed = !bouundary_vertices_are_reversed;std::swap(boundary_left, boundary_right);data.reverse();if(node_type == NODE_TYPE_COMPRESS){std::swap(left_child, right_child);}}void apply_lazy_data(TopTreeClusterEffect f){lazy_data = TopTreeClusterEffect::composition(f, lazy_data);data = TopTreeClusterEffect::mapping_cluster(f, data);}void lazy_propagation(){if(bouundary_vertices_are_reversed){if(node_type == NODE_TYPE_COMPRESS){left_child->reverse_boundary_vertices();right_child->reverse_boundary_vertices();}}bouundary_vertices_are_reversed = false;auto f = lazy_data;if(node_type == NODE_TYPE_COMPRESS){left_child->apply_lazy_data(f);if(mid_child){mid_child->apply_lazy_data(f);mid_child->boundary_left->data = TopTreeClusterEffect::mapping_vertex(f, mid_child->boundary_left->data);}right_child->apply_lazy_data(f);left_child->boundary_right->data = TopTreeClusterEffect::mapping_vertex(f, left_child->boundary_right->data);}if(node_type == NODE_TYPE_RAKE){left_child->apply_lazy_data(f);right_child->apply_lazy_data(f);right_child->boundary_left->data = TopTreeClusterEffect::mapping_vertex(f, right_child->boundary_left->data);}lazy_data = TopTreeClusterEffect::id();}void bottomup_edge(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, TopTreeClusterData x){node_type = NODE_TYPE_EDGE;left_child = nullptr;right_child = nullptr;mid_child = nullptr;boundary_left = l;boundary_right = r;l->handle = this;r->handle = this;data = x;lazy_data = TopTreeClusterEffect::id();}void bottomup_rake(TopTreeNode* l, TopTreeNode* r, bool special_for_hard_expose = false){if(l->node_type != NODE_TYPE_RAKE) l->boundary_left->handle = l;if(r->node_type != NODE_TYPE_RAKE) r->boundary_left->handle = r;if (!special_for_hard_expose) {node_type = NODE_TYPE_RAKE;boundary_left = l->boundary_left;boundary_right = l->boundary_right;left_child = l;l->parent = this;mid_child = nullptr;right_child = r;r->parent = this;data = TopTreeClusterData::rake(left_child->data, right_child->data, right_child->boundary_left->data);}else {node_type = NODE_TYPE_RAKE;boundary_left = l->boundary_left;boundary_right = l->boundary_right;left_child = l;l->parent = this;mid_child = nullptr;right_child = r;r->parent = this;auto buf = left_child->data;buf.reverse();buf = TopTreeClusterData::rake(buf, right_child->data, right_child->boundary_left->data);buf.reverse();data = buf;}}void bottomup_compress(TopTreeNode* l, TopTreeNode* m_rake, TopTreeNode* r){assert(l->boundary_right == r->boundary_left);UnderlyingTreeVertex* bound = l->boundary_right;node_type = NODE_TYPE_COMPRESS;boundary_left = l->boundary_left;boundary_right = r->boundary_right;left_child = l;l->parent = this;mid_child = m_rake;if(m_rake) m_rake->parent = this;right_child = r;r->parent = this;if(mid_child && mid_child->node_type != NODE_TYPE_RAKE) mid_child->boundary_left->handle = mid_child;boundary_left->handle = this;bound->handle = this;boundary_right->handle = this;auto cent = left_child->boundary_right;auto l_data = left_child->data;if (mid_child) l_data = TopTreeClusterData::rake(l_data, mid_child->data, mid_child->boundary_left->data);data = TopTreeClusterData::compress(l_data, cent->data, right_child->data);}void rotate_rake_left(){auto p = parent;if(!p->is_root()) p->parentchild() = this;parent = p->parent;auto c1 = left_child;p->bottomup_rake(p->left_child, c1);bottomup_rake(p, right_child);}void rotate_rake_right(){auto p = parent;if(!p->is_root()) p->parentchild() = this;parent = p->parent;auto c1 = right_child;p->bottomup_rake(c1, p->right_child);bottomup_rake(left_child, p);}void rotate_compress_left(){auto p = parent;if(!p->is_root()) p->parentchild() = this;parent = p->parent;auto c4 = this->left_child;p->bottomup_compress(p->left_child, p->mid_child, c4);bottomup_compress(p, mid_child, right_child);}void rotate_compress_right(){auto p = parent;if(!p->is_root()) p->parentchild() = this;parent = p->parent;auto c3 = this->right_child;p->bottomup_compress(c3, p->mid_child, p->right_child);bottomup_compress(left_child, mid_child, p);}void splay_soft_rake(){while(!is_rake_root()){auto p = parent;if(p->is_rake_root()){if(p->left_child == this){ rotate_rake_right(); }else{ rotate_rake_left(); }}else{auto pp = p->parent;if(p->left_child == this){if(pp->left_child == p){ p->rotate_rake_right(); rotate_rake_right(); }else { rotate_rake_right(); rotate_rake_left(); }}else{if(pp->right_child == p){ p->rotate_rake_left(); rotate_rake_left(); }else { rotate_rake_left(); rotate_rake_right(); }}}}}void splay_rake(){if(is_rake_root()) return;auto p1 = parent;p1->splay_soft_rake();auto p2 = parent;if(p2 == p1) return;p2->splay_soft_rake();}void splay_compress(){while(!is_compress_root()){auto p = parent;if(p->is_compress_root()){if(p->left_child == this){ rotate_compress_right(); }else{ rotate_compress_left(); }}else{auto pp = p->parent;if(p->left_child == this){if(pp->left_child == p){ p->rotate_compress_right(); rotate_compress_right(); }else { rotate_compress_right(); rotate_compress_left(); }}else{if(pp->right_child == p){ p->rotate_compress_left(); rotate_compress_left(); }else { rotate_compress_left(); rotate_compress_right(); }}}}}void splice(bool compress_on_left = true){TopTreeNode* p = nullptr;TopTreeNode* rake_l = nullptr;TopTreeNode* rake_lp = nullptr;TopTreeNode* rake_r = nullptr;TopTreeNode* rake_rp = nullptr;p = parent;bool is_this_left_child = (p->left_child == this);while(p->node_type == NODE_TYPE_RAKE){if(is_this_left_child){rake_r = p->right_child;rake_rp = p;}else{rake_l = p->left_child;rake_lp = p;}auto pp = p->parent;is_this_left_child = (pp->left_child == p);p = pp;}if(compress_on_left){auto rake_r1 = p->left_child;if(rake_l){ rake_lp->bottomup_rake(rake_l, rake_r1); rake_r1 = rake_lp; }if(rake_r){ rake_rp->bottomup_rake(rake_r1, rake_r); rake_r1 = rake_rp; }p->bottomup_compress(this, rake_r1, p->right_child);}else{reverse_boundary_vertices();auto rake_r1 = p->right_child;rake_r1->reverse_boundary_vertices();if(rake_l){ rake_lp->bottomup_rake(rake_l, rake_r1); rake_r1 = rake_lp; }if(rake_r){ rake_rp->bottomup_rake(rake_r1, rake_r); rake_r1 = rake_rp; }p->bottomup_compress(p->left_child, rake_r1, this);}}bool is_enabled() const { return node_type != NODE_TYPE_DISABLED; }bool is_rake_root() const { return !parent || parent->node_type != NODE_TYPE_RAKE; }bool is_compress_root() const {if(!parent) return true;if(parent->node_type != NODE_TYPE_COMPRESS) return true;return parent->mid_child == this;}bool is_root() const { return !parent; }};struct UnderlyingTreeVertex{TopTreeNode* handle;TopTreeVertexData data;UnderlyingTreeVertex(){handle = nullptr;data = TopTreeVertexData::init();}void exposing_target(){TopTreeNode* n_this = handle;handle->get_propagated();auto c = n_this;while(!c->is_root()){if(!c->is_compress_root()){c->splay_compress();continue;}if(!c->is_rake_root()){c->splay_rake();while(!c->is_rake_root()) c = c->parent;continue;}c = c->parent;}c = n_this = handle;while(!c->is_root()){c->splice();c = c->parent;}handle->get_propagated();handle->splay_compress();}bool exposing_source(UnderlyingTreeVertex* target){auto n_this = handle;auto n_target = target->handle;if(n_this == n_target) return true;if(n_target->node_type == TopTreeNode::NODE_TYPE_EDGE) return false;if(n_this->is_root()) return false;if(n_target->boundary_left == target) n_target->reverse_boundary_vertices();if(n_target->boundary_right == target){exposing_target();return true;}handle->get_propagated();// blockn_target->left_child->parent = nullptr;n_target->right_child->parent = nullptr;auto c = n_this;while(!c->is_root()){if(!c->is_compress_root()){c->splay_compress();continue;}if(!c->is_rake_root()){c->splay_rake();while(!c->is_rake_root()) c = c->parent;continue;}c = c->parent;}if (!n_target->left_child->is_root()) n_target->left_child = c;if (!n_target->right_child->is_root()) n_target->right_child = c;c = n_this = handle;while(!c->is_root()){auto p = c;while(!p->is_rake_root()) p = p->parent;bool compress_to_left = true;if(n_target->right_child == p->parent) compress_to_left = false;c->splice(compress_to_left);c = c->parent;if(n_target == c){n_target->left_child->parent = nullptr;n_target->right_child->parent = nullptr;}}c = handle;c->get_propagated();c->splay_compress();if (!n_target->left_child->is_root()) n_target->left_child = c;if (!n_target->right_child->is_root()) n_target->right_child = c;n_target->bottomup_compress(n_target->left_child, n_target->mid_child, n_target->right_child);if(c->is_root()) return false;if(n_target->right_child == c){n_target->reverse_boundary_vertices();n_target->lazy_propagation();}return true;}};TopTreeNode* expose(UnderlyingTreeVertex* l){undo_hard_expose();if(!l->handle) return nullptr;UnderlyingTreeVertex* r = nullptr;if(l->handle->boundary_left != l) r = l->handle->boundary_left;if(l->handle->boundary_right != l) r = l->handle->boundary_right;return expose(l, r);}TopTreeNode* expose(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, bool do_hard = true){undo_hard_expose();// soft exposesoft_expose(l, r);auto n_l = l->handle;auto n_r = r->handle;// hard exposeif(do_hard){auto hard_expose_rake_case1 = [this](TopTreeNode* c)->void {hard_expose_undo_memo[hard_expose_undo_length++] = HardExposeUndoUnit(c);hard_expose_undo_memo[hard_expose_undo_length - 1].r_reversed = true;c->right_child->reverse_boundary_vertices();TopTreeNode* rake_r = c->right_child;if(c->mid_child){auto tmp = new TopTreeNode();tmp->bottomup_rake(c->mid_child, rake_r);rake_r = tmp;hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(rake_r, true);}c->bottomup_rake(c->left_child, rake_r, false);hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(c, false);};auto hard_expose_rake_case2 = [this](TopTreeNode* c)->void {hard_expose_undo_memo[hard_expose_undo_length++] = HardExposeUndoUnit(c);TopTreeNode* rake_r = c->left_child;if(c->mid_child){auto tmp = new TopTreeNode();tmp->bottomup_rake(rake_r, c->mid_child);rake_r = tmp;hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(rake_r, true);}c->bottomup_rake(c->right_child, rake_r, true);hard_expose_new_rakes[hard_expose_new_rakes_length++] = std::make_pair(c, false);};n_r->lazy_propagation();n_l->lazy_propagation();if(n_r->boundary_left == l && n_r->boundary_right == r){ /* case (3) (4) do nothing */ }else if(n_r->boundary_left == l){ /* case (1) */ hard_expose_rake_case1(n_r); }else if(n_r->boundary_right == r){ /* case (2) */ hard_expose_rake_case2(n_r); }else{ /* case (5) */ hard_expose_rake_case2(n_l); hard_expose_rake_case1(n_r); }}return n_r;}bool cut(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, TopTreeClusterData* data_out){undo_hard_expose();auto fix_tmporary_state = [this](TopTreeNode* c)->TopTreeNode*{if(c->mid_child){if(c->mid_child->node_type == TopTreeNode::NODE_TYPE_RAKE){// case (3)auto most_left_rake = c->mid_child;most_left_rake->lazy_propagation();while(most_left_rake->left_child->node_type == TopTreeNode::NODE_TYPE_RAKE){most_left_rake = most_left_rake->left_child;most_left_rake->lazy_propagation();}most_left_rake->splay_soft_rake();most_left_rake = most_left_rake->left_child;most_left_rake->reverse_boundary_vertices();c->bottomup_compress(c->left_child, c->mid_child->right_child, most_left_rake);}else{// case (2)c->mid_child->reverse_boundary_vertices();c->bottomup_compress(c->left_child, nullptr, c->mid_child);}}else{// case (1)auto cc = c->left_child;cc->parent = nullptr;delete(c);c = cc;c->boundary_left->handle = c;c->boundary_right->handle = c;}return c;};soft_expose(l, r);auto n_l = l->handle;auto n_r = r->handle;if(n_r->node_type == TopTreeNode::NODE_TYPE_EDGE){// case (4)l->handle = r->handle = nullptr;if(data_out) *data_out = n_l->data;delete(n_l);return true;}if(n_r->boundary_left == l && n_r->boundary_right == r){// case (3)return false;}if(n_r->boundary_left == l){// case (1)n_r->reverse_boundary_vertices();std::swap(l, r);// reduce to case (2)}if(n_r->boundary_right == r){// case (2)n_r->lazy_propagation();auto lr = n_r->right_child;if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;if(data_out) *data_out = lr->data;delete(lr);n_r->right_child = nullptr;fix_tmporary_state(n_r);r->handle = nullptr;return true;}// case (5)n_r->lazy_propagation();n_l->lazy_propagation();auto lr = n_l->right_child;if(lr->node_type != TopTreeNode::NODE_TYPE_EDGE) return false;if(data_out) *data_out = lr->data;delete(lr);n_r->left_child = nullptr;n_l->right_child = nullptr;n_l->parent = nullptr;fix_tmporary_state(n_l);n_r->left_child = n_r->right_child;n_r->left_child->reverse_boundary_vertices();fix_tmporary_state(n_r);return true;}bool link(UnderlyingTreeVertex* l, UnderlyingTreeVertex* r, TopTreeClusterData x){undo_hard_expose();auto make_temporary_state = [this](UnderlyingTreeVertex* c)->TopTreeNode* {auto n_c = c->handle;if(n_c->boundary_left == c){n_c->reverse_boundary_vertices();}if(n_c->boundary_right == c){// c is a leafauto unstable_root = new TopTreeNode();n_c->parent = unstable_root;unstable_root->left_child = n_c;return unstable_root;}// c is not a leafn_c->lazy_propagation();auto r_rake = n_c->right_child;n_c->right_child = nullptr;r_rake->reverse_boundary_vertices();if(n_c->mid_child){auto rake_root = new TopTreeNode();rake_root->bottomup_rake(n_c->mid_child, r_rake);r_rake = rake_root;}n_c->mid_child = r_rake;r_rake->parent = n_c;n_c->node_type = TopTreeNode::NODE_TYPE_DISABLED;return n_c;};if(!l->handle) std::swap(l, r);if(!l->handle){// cut case (4)TopTreeNode* c = new TopTreeNode();c->bottomup_edge(l, r, x);return true;}if(!r->handle){// r->handle == nullptr : cut case (2)l->exposing_target();auto n_l = make_temporary_state(l);auto lr = new TopTreeNode();lr->bottomup_edge(l, r, x);n_l->bottomup_compress(n_l->left_child, n_l->mid_child, lr);return true;}// cut case (5)l->exposing_target();r->exposing_target();if(l->handle == r->handle) return false;if(!l->handle->is_root()) return false;auto n_l = make_temporary_state(l);auto n_r = make_temporary_state(r);std::swap(n_r->left_child, n_r->right_child);n_r->right_child->reverse_boundary_vertices();auto lr = new TopTreeNode();lr->bottomup_edge(l, r, x);n_r->bottomup_compress(lr, n_r->mid_child, n_r->right_child);n_l->bottomup_compress(n_l->left_child, n_l->mid_child, n_r);return true;}struct HardExposeUndoUnit{TopTreeNode* to = nullptr;TopTreeNode* l = nullptr;bool l_reversed = false;TopTreeNode* m_rake = nullptr;bool m_rake_reversed = false;TopTreeNode* r = nullptr;bool r_reversed = false;HardExposeUndoUnit(){}HardExposeUndoUnit(TopTreeNode* v){to = v;l = v->left_child;m_rake = v->mid_child;r = v->right_child;}void execute(){if (l_reversed) l->reverse_boundary_vertices();if (m_rake_reversed) m_rake->reverse_boundary_vertices();if (r_reversed) r->reverse_boundary_vertices();to->bottomup_compress(l, m_rake, r);}};int hard_expose_undo_length = 0;HardExposeUndoUnit hard_expose_undo_memo[2];int hard_expose_new_rakes_length = 0;std::pair<TopTreeNode*, bool> hard_expose_new_rakes[10] = {};};#include <vector>#include <algorithm>namespace nachia {struct Dsu{private:int N;std::vector<int> P;std::vector<int> H;public:Dsu() : N(0) {}Dsu(int n) : N(n), P(n, -1), H(n) {for(int i=0; i<n; i++) H[i] = i;}int leader(int u){if(P[u] < 0) return u;int v = P[u];while(P[v] >= 0){ P[u] = P[v]; u = v; v = P[v]; }return P[u];}int append(){int n = P.size();P.push_back(-1);H.push_back(n);return n;}int label(int u){ return H[leader(u)]; }int operator[](int u){ return H[leader(u)]; }void merge(int u, int v, int newLabel){if(newLabel < 0) newLabel = u;u = leader(u);v = leader(v);if(u == v){ H[u] = newLabel; return; }N--;if(-P[u] < -P[v]) std::swap(u, v);P[u] += P[v];H[P[v] = u] = newLabel;}int merge(int u, int v){ merge(u, v, u); return u; }int count(){ return N; }int size(int u){ return -P[leader(u)]; }bool same(int u, int v){ return leader(u) == leader(v); }};} // namespace nachiastruct TopTreeVertexData{static TopTreeVertexData init(){ return {}; }};struct TopTreeClusterData{long long l, r, len, diam;static TopTreeClusterData edge(long long w){return { w, w, w, w };}static TopTreeClusterData init(){ return { 0,0,0,0 }; }static TopTreeClusterData compress(TopTreeClusterData l, TopTreeVertexData, TopTreeClusterData r){return {std::max(l.l, l.len + r.l),std::max(r.r, r.len + l.r),l.len + r.len,std::max(std::max(l.diam, r.diam), l.r + r.l)};}static TopTreeClusterData rake(TopTreeClusterData l, TopTreeClusterData r, TopTreeVertexData){return {std::max(l.l, l.len + r.r),std::max(l.r, r.r),l.len,std::max(std::max(l.diam, r.diam), l.r + r.r)};}void reverse(){std::swap(l, r);}};struct TopTreeClusterEffect{static TopTreeClusterEffect id(){ return { }; }static TopTreeClusterData mapping_cluster(TopTreeClusterEffect, TopTreeClusterData x){return x;}static TopTreeVertexData mapping_vertex(TopTreeClusterEffect, TopTreeVertexData x){return x;}static TopTreeClusterEffect composition(TopTreeClusterEffect l, TopTreeClusterEffect){return { l };}void reverse(){}};#include <iostream>using namespace std;#define rep(i,n) for(int i=0; i<(int)(n); i++)int main(){ios::sync_with_stdio(false);cin.tie(nullptr);long long N, X, Q; cin >> N >> X >> Q;using TopTreeInst = TopTree<TopTreeVertexData, TopTreeClusterData, TopTreeClusterEffect>;TopTreeInst toptree;vector<TopTreeInst::UnderlyingTreeVertex> vtxs(N);auto dsu = nachia::Dsu(N);rep(i,Q){int t; cin >> t;if(t == 1){int v, w; cin >> v >> w;toptree.link(&vtxs[X], &vtxs[v], TopTreeClusterData::edge(w));dsu.merge(v, X);}if(t == 2){int u, v; cin >> u >> v;if(!dsu.same(u, v)){cout << "-1\n";}else if(u == v){cout << 0 << '\n';}else{long long x = toptree.expose(&vtxs[u], &vtxs[v])->data.len;X = (X + x) % N;cout << x << '\n';}}if(t == 3){int v; cin >> v;if(dsu.size(v) == 1){cout << "0\n";}else{auto c = toptree.expose(&vtxs[v]);cout << c->data.diam << '\n';}}if(t == 4){long long v; cin >> v;X = (X + v) % N;}}}