Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3653

Problem Lang User Status Time Memory
Lowest Common Ancestor cpp14 yamate11 AC 1859 ms 185.62 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.62 MiB
line_00 AC 1175 ms 156.66 MiB
line_01 AC 1282 ms 185.62 MiB
line_02 AC 592 ms 23.12 MiB
line_03 AC 482 ms 169.82 MiB
line_04 AC 446 ms 110.38 MiB
random_00 AC 1585 ms 104.49 MiB
random_01 AC 1859 ms 125.58 MiB
random_02 AC 578 ms 15.48 MiB
random_03 AC 1162 ms 114.11 MiB
random_04 AC 756 ms 74.04 MiB

#include <bits/stdc++.h> #include <cassert> typedef long long int ll; using namespace std; // @@ !! LIM(tree) // --> f:updMaxMin tree // ---- inserted function updMaxMin from util.cc template<typename T> bool updMax(T& tmax, const T& x) { if (x > tmax) { tmax = x; return true; } else { return false; } } template<typename T> bool updMin(T& tmin, const T& x) { if (x < tmin) { tmin = x; return true; } else { return false; } } // ---- end updMaxMin // ---- inserted library file tree.cc class Edge : public pair<int, int> { public: Edge() : pair<int, int>() {} Edge(const int& x, const int& y) : pair<int, int>(x, y) {} Edge(istream& stream, int shift) { stream >> this->first >> this->second; this->first -= shift; this->second -= shift; } }; class Tree { void init() { numNodes = edge.size() + 1; for (int i = 0; i < numNodes - 1; i++) { Edge e = edge.at(i); node2edge[e.first][e.second] = node2edge[e.second][e.first] = i; } auto dfs = [&](const auto& recF, int n, int p, int l) -> void { parent.at(n) = p; depth.at(n) = l; for (auto c : node2edge[n]) { if (c.first == p) continue; child.at(n).push_back(c.first); recF(recF, c.first, n, l+1); } }; parent.resize(numNodes); child.resize(numNodes); depth.resize(numNodes); dfs(dfs, root, -1, 0); parent.at(root) = root; } vector<vector<int>> pPnt; // pPnt.at(0) == parent // pPnt.at(t).at(n) == parent^{2^t}.at(n) void preparePPnt() { pPnt.push_back(parent); for (int t = 0; true; t++) { bool done = true; vector<int> vec(numNodes); for (int n = 0; n < numNodes; n++) { int m = pPnt.at(t).at(n); vec.at(n) = pPnt.at(t).at(m); if (vec.at(n) != m) done = false; } pPnt.push_back(move(vec)); if (done) break; } } public: int numNodes; int root; vector<int> parent; // parent.at(root) == root vector<vector<int>> child; vector<int> depth; vector<Edge> edge; map<int, map<int, int>> node2edge; Tree(vector<Edge>&& edge_, int root_ = 0) : root(root_), edge(move(edge_)) { init(); } Tree(const auto& edge_, int root_ = 0) : root(root_), edge() { for (Edge e : edge_) edge.push_back(e); init(); } // Lowest Common Ancestor int lca(int x, int y) { if (depth.at(x) > depth.at(y)) swap(x, y); int dep = depth.at(x); int yy = ancestorDep(y, dep); if (x == yy) return x; int t = 0; for (int q = 1; q < dep; q *= 2) t++; for ( ; t >= 0; t--) { if (pPnt.at(t).at(x) != pPnt.at(t).at(yy)) { x = pPnt.at(t).at(x); yy = pPnt.at(t).at(yy); } } return parent.at(x); } // the path between two nodes vector<int> nnpath(int x, int y) { vector<int> ret, sub; int c = lca(x, y); for ( ; x != c; x = parent.at(x)) ret.push_back(x); for ( ; y != c; y = parent.at(y)) sub.push_back(y); ret.push_back(c); for (int i = sub.size() - 1; i >= 0; i--) ret.push_back(sub.at(i)); return ret; } // the ancestor of n whose depth is dep int ancestorDep(int n, int dep) { if (pPnt.size() == 0) preparePPnt(); int diff = depth.at(n) - dep; assert(diff >= 0); for (int t = 0; diff > 0; t++) { if (diff & (1 << t)) { n = pPnt.at(t).at(n); diff ^= (1 << t); } } return n; } #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-but-set-variable" // diameter // not efficient at all. fixed-rooted tree is not suitable.... int diameter() { // tuple<int, int, int> diameter() { int maxDepth = 0; int mdArg1; for (int i = 0; i < numNodes; i++) { if (updMax(maxDepth, depth.at(i))) mdArg1 = i; } Tree tr2(edge, mdArg1); maxDepth = 0; int mdArg2; for (int i = 0; i < numNodes; i++) { if (updMax(maxDepth, tr2.depth.at(i))) mdArg2 = i; } // Return mdArg1 and mdArg2 if you need endpoints as well. // return make_pair(maxDepth, mdArg1, mdArg2); return maxDepth; } }; #pragma GCC diagnostic pop // ---- end tree.cc // @@ !! LIM -- end mark -- int main(int argc, char *argv[]) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << setprecision(20); ll N, Q; cin >> N >> Q; vector<Edge> ve; for (ll i = 1; i <= N-1; i++) { ll p; cin >> p; ve.emplace_back(p, i); } Tree tr(move(ve)); for (ll i = 0; i < Q; i++) { ll u, v; cin >> u >> v; cout << tr.lca(u, v) << endl; } return 0; }