# 33 and Least Common Ancestor (LCA) Problem

I finally did it! The one-armed pull up. There's a bit of a kip, but I'll take it.

Despite my best years being behind me, it's still good to see progress. I have somewhat dispensed with the fake humility. As I find myself getting older, I appreciate clarity and directness more and being honest with myself. I am proud of this whether anyone else cares or not, so I am going to share it. Now, if I could only actually climb.

A lot of taking myself less seriously comes from the daily humiliations brought about by life as 30-something bachelor in NYC. Being stood up and ghosted is just par for the week now. But I am learning to understand that some people just need space to deal with their problems, and some people are just terrible, too.

Another area where I've grown in is how I write code. In Minimum Spanning Trees and the Least Common Ancestor Problem, I described a binary lifting algorithm to find the least common ancestor. I tried way too hard to impress and now I can't figure out what I wrote.

I recently needed this algorithm again in 2322. Minimum Score After Removals on a Tree . If I had a simple implementation that I could understand and reuse, I may have been able to solve it during the contest, so now, I rewrote it.

``````#include <algorithm>
#include <limits>
#include <vector>

class Solution {
public:
int minimumScore(const std::vector<int>& nums,
const std::vector<std::vector<int>>& edges);
};

namespace {

void RootTree(const std::vector<std::vector<int>>& adjacency_list, int root,
std::vector<int>* depths, std::vector<int>* parents,
std::vector<int>* xors) {
for (auto child : adjacency_list[root]) {
if (child == (*parents)[root]) continue;
(*depths)[child] = (*depths)[root] + 1;
(*parents)[child] = root;
RootTree(adjacency_list, child, depths, parents, xors);
(*xors)[root] ^= (*xors)[child];
}
}

void BuildAncestors(std::vector<std::vector<int>>* ancestors) {
bool built = true;
for (auto& as : *ancestors) {
const int a = as.back();
if (a == -1) continue;
const int j = as.size() - 1;
as.push_back(j < (*ancestors)[a].size() ? (*ancestors)[a][j] : -1);
built = false;
}
if (!built) BuildAncestors(ancestors);
}

int LeastCommonAncestor(const std::vector<std::vector<int>>& ancestors,
const std::vector<int>& depth, int u, int v) {
if (u == v) return u;
int delta = depth[v] - depth[u];
if (delta == 0) {
int j = 0;
while (ancestors[u][j + 1] != -1 &&
ancestors[u][j + 1] != ancestors[v][j + 1])
++j;
return LeastCommonAncestor(ancestors, depth, ancestors[u][j],
ancestors[v][j]);
}
if (delta < 0) {
std::swap(u, v);
delta = -delta;
}
int j = 0;
while (1 << (j + 1) <= delta) ++j;
return LeastCommonAncestor(ancestors, depth, u, ancestors[v][j]);
}

}  // namespace

int Solution::minimumScore(const std::vector<int>& nums,
const std::vector<std::vector<int>>& edges) {
const int n = nums.size();
// Root the tree at 0 and compute properties based on that.
for (const auto& edge : edges) {
}
std::vector<int> depths(n, 0);
std::vector<int> parents(n, -1);
std::vector<int> xors = nums;
RootTree(adjacency_list, 0, &depths, &parents, &xors);
// ancestors[i][j] is the 2^j ancestor of node i.
std::vector<std::vector<int>> ancestors;
ancestors.reserve(n);
for (int i = 0; i < n; ++i) ancestors.push_back({parents[i]});
BuildAncestors(&ancestors);
// Determine minimum score by looping over all pairs of edges.
int min_score = std::numeric_limits<int>::max();
for (int i = 1; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
const int u = depths[i] <= depths[j] ? i : j;
const int v = depths[i] <= depths[j] ? j : i;
const int ancestor = LeastCommonAncestor(ancestors, depths, u, v);
const int xor0 =
ancestor == u ? xors[0] ^ xors[u] : xors[0] ^ xors[u] ^ xors[v];
const int xor1 = ancestor == u ? xors[u] ^ xors[v] : xors[u];
const int xor2 = xors[v];
min_score = std::min(min_score, std::max(xor0, std::max(xor1, xor2)) -
std::min(xor0, std::min(xor1, xor2)));
}
}
return min_score;
}
``````