说我们有一棵有向树（有向图）。因此，随着时间的流逝，我们将在主分支上构建，将主分支定义为距根（整个树的第一个节点）最长的分支，并且在构建它时，我们可以随时构建新分支通过将新节点附加到任意节点，但是在大多数情况下，我们基于尖端（在最长分支上）。
图形节点的格式为：
struct {
int id;
int prev_node_id; // this is what links nodes together
}
假设我们选择两个随机节点X和Y。问题是：这些节点是否共享分支？
每个节点都由ID定义（基本上是加密哈希，在此由int简化）。解决此问题的一种方法是，我们仅从一个节点开始返回图，直到遇到另一个节点。这需要循环遍历分支中的所有节点，因此这是O（N），其中N是分支中的节点数，这可能非常非常长（数百万个节点）。我们可以在可进行此操作的节点中构建任何类型的数据O（1），而每个节点的大小也为O（1）？]
我的解决方案第一（不好，因为每个节点的存储量为O（N）：
我们在数据结构中添加一个任意的长质数：
struct {
int id;
int prev_node_id;
ArbitraryPrecisionInt branch_index;
}
[每当将节点附加到树的任何部分时，我们都将branch_index定义为：
branch_index_new = branch_index_old * new_prime_number;
其中新质数来自单例生成器。假设我们有几百万个节点，这并不算昂贵。至少还算不错。
所以，节点X和Y共享相同的分支吗？
如果满足以下条件，则答案为是：X % Y == 0或Y % X == 0。
这里的问题是，该产品的尺寸将增长很快。前1000个质数的乘积巨大。
我的解决方案第二（有点不好，因为它在搜索时间上是O（log（N）），但每个节点的存储量是O（1））：
struct {
int id;
int prev_node_id;
int branch_id;
}
branch_id基本上来自单例。我们从0开始，对于我们创建的每个新节点，都有两种情况。
[之后，我们创建一个数据库表，在其中写入每个新增量与每个值的高度（将高度定义为从根节点到该节点的长度）。
因此，节点X和Y是否共享相同的分支？为了回答这个问题，我们先查看X的branch_id，然后查看数据库，然后找到创建分支的高度。我们去那里，找到之前的点的branch_id。我们一直这样做，直到到达根（失败）或找到Y的branch_id。
整个故事是我正在尝试解决的区块链问题。实际问题的细节确实很复杂，没有必要去做。但是，如果您有兴趣，随时与我聊天。我说这是因为肯定有人会将此称为XY问题。
还有更好的方法吗？
说我们有一棵有向树（有向图）。因此，随着时间的流逝，我们将建立在主分支上，在主分支中，我们将主分支定义为从根（整棵树的第一个节点）开始的最长分支，然后...
只是为了清除术语：在树上添加叶子时，您希望能够选择任意两个节点并确定一个节点是否是另一个节点的祖先。