This documentation is automatically generated by competitive-verifier/competitive-verifier
#include <bits/stdc++.h>
#include "LCA.cpp"
using namespace std;
struct auxiliary_tree : lca_tree {
vector<vector<int>> G;
auxiliary_tree(vector<vector<int>>& g) : lca_tree(g), G(n) {}
pair<int, vector<int>> query(vector<int> vs, bool decending = false) {
// decending:親から子の方向のみ辺を貼る
assert(!vs.empty());
sort(vs.begin(), vs.end(), [&](int a, int b) { return in[a] < in[b]; });
int m = vs.size();
stack<int> st;
st.push(vs[0]);
for (int i = 0; i < m - 1; i++) {
int w = lca(vs[i], vs[i + 1]);
if (w != vs[i]) {
int l = st.top();
st.pop();
while (!st.empty() && depth[w] < depth[st.top()]) {
if (!decending) G[l].push_back(st.top());
G[st.top()].push_back(l);
l = st.top();
st.pop();
}
if (st.empty() || st.top() != w) {
st.push(w);
vs.push_back(w);
}
if (!decending) G[l].push_back(w);
G[w].push_back(l);
}
st.push(vs[i + 1]);
}
while (st.size() > 1) {
int x = st.top();
st.pop();
if (!decending) G[x].push_back(st.top());
G[st.top()].push_back(x);
}
// {root,vertex_list}
return make_pair(st.top(), vs);
}
void clear(vector<int> vs) {
for (int v : vs) G[v].clear();
}
};
#line 1 "AuxiliaryTree.cpp"
#include <bits/stdc++.h>
#line 2 "SparseTable.cpp"
using namespace std;
template <class T, T (*op)(T, T), T (*e)()>
struct sparsetable {
vector<vector<T>> table;
vector<int> logtable;
sparsetable() = default;
sparsetable(vector<T> v) {
int len = 0;
while ((1 << len) <= (int)v.size()) len++;
table.assign(len, vector<T>(1 << len));
for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
for (int i = 1; i < len; i++) {
for (int j = 0; j + (1 << i) <= (1 << len); j++) {
table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
logtable.resize((int)v.size() + 1);
for (int i = 2; i < (int)logtable.size(); i++) {
logtable[i] = logtable[(i >> 1)] + 1;
}
}
T query(int l, int r) {
assert(l <= r);
if (l == r) return e();
int len = logtable[r - l];
return op(table[len][l], table[len][r - (1 << len)]);
}
};
template <class T, T (*op)(T, T), T (*e)()>
struct disjointsparsetable {
vector<vector<T>> table;
vector<int> logtable;
disjointsparsetable() = default;
disjointsparsetable(vector<T> v) {
int len = 0;
while ((1 << len) <= v.size()) len++;
table.assign(len, vector<T>(1 << len, e()));
for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
for (int i = 1; i < len; i++) {
int shift = 1 << i;
for (int j = 0; j < (int)v.size(); j += shift << 1) {
int t = min(j + shift, (int)v.size());
table[i][t - 1] = v[t - 1];
for (int k = t - 2; k >= j; k--) table[i][k] = op(v[k], table[i][k + 1]);
if (v.size() <= t) break;
table[i][t] = v[t];
int r = min(t + shift, (int)v.size());
for (int k = t + 1; k < r; k++) table[i][k] = op(table[i][k - 1], v[k]);
}
}
logtable.resize(1 << len);
for (int i = 2; i < logtable.size(); i++) {
logtable[i] = logtable[(i >> 1)] + 1;
}
}
T query(int l, int r) {
if (l == r) return e();
if (l >= --r) return table[0][l];
int len = logtable[l ^ r];
return op(table[len][l], table[len][r]);
};
};
#line 3 "LCA.cpp"
using namespace std;
pair<int, int> lcatree_op(pair<int, int> a, pair<int, int> b) { return min(a, b); }
pair<int, int> lcatree_e() { return {1000000000, -1}; }
struct lca_tree {
int n, size;
vector<int> in, ord, depth;
disjointsparsetable<pair<int, int>, lcatree_op, lcatree_e> st;
lca_tree(vector<vector<int>> g, int root = 0) : n((int)g.size()), size(log2(n) + 2), in(n), depth(n, n) {
depth[root] = 0;
function<void(int, int)> dfs = [&](int v, int p) {
in[v] = (int)ord.size();
ord.push_back(v);
for (int u : g[v]) {
if (u == p) continue;
if (depth[u] > depth[v] + 1) {
depth[u] = depth[v] + 1;
dfs(u, v);
ord.push_back(v);
}
}
};
dfs(root, -1);
vector<pair<int, int>> vec((int)ord.size());
for (int i = 0; i < (int)ord.size(); i++) {
vec[i] = make_pair(depth[ord[i]], ord[i]);
}
st = vec;
}
int lca(int u, int v) {
if (in[u] > in[v]) swap(u, v);
if (u == v) return u;
return st.query(in[u], in[v]).second;
}
int dist(int u, int v) {
int l = lca(u, v);
return depth[u] + depth[v] - 2 * depth[l];
}
};
#line 3 "AuxiliaryTree.cpp"
using namespace std;
struct auxiliary_tree : lca_tree {
vector<vector<int>> G;
auxiliary_tree(vector<vector<int>>& g) : lca_tree(g), G(n) {}
pair<int, vector<int>> query(vector<int> vs, bool decending = false) {
// decending:親から子の方向のみ辺を貼る
assert(!vs.empty());
sort(vs.begin(), vs.end(), [&](int a, int b) { return in[a] < in[b]; });
int m = vs.size();
stack<int> st;
st.push(vs[0]);
for (int i = 0; i < m - 1; i++) {
int w = lca(vs[i], vs[i + 1]);
if (w != vs[i]) {
int l = st.top();
st.pop();
while (!st.empty() && depth[w] < depth[st.top()]) {
if (!decending) G[l].push_back(st.top());
G[st.top()].push_back(l);
l = st.top();
st.pop();
}
if (st.empty() || st.top() != w) {
st.push(w);
vs.push_back(w);
}
if (!decending) G[l].push_back(w);
G[w].push_back(l);
}
st.push(vs[i + 1]);
}
while (st.size() > 1) {
int x = st.top();
st.pop();
if (!decending) G[x].push_back(st.top());
G[st.top()].push_back(x);
}
// {root,vertex_list}
return make_pair(st.top(), vs);
}
void clear(vector<int> vs) {
for (int v : vs) G[v].clear();
}
};