Readme

2846.Minimum-Edge-Weight-Equilibrium-Queries-in-a-Tree

我们以任意节点作为根（比如说0号节点），将整张图看成一棵从上往下有向的树。因为边权的种类只有26个，我们可以用一遍DFS，记录下根到每个节点的路径所包含了的边权种类及其数目。我们记做count[i][j]，表示根到节点i的路径中，第j种边权出现了多少次。

对于query里的两个节点p、q，我们如果能找到他们的最小公共节点lca，那么就可以得到p->q路径上的每种边权数目，即count[p][j]+count[q][j]-2*count[lca][j]，我们遍历一下j，就可以知道路径长度以及出现最多次的边权个数，两者之差就是query的答案。

那么如何求lca呢？我们需要在DFS的过程中，顺便知道每个节点的深度level[i]以及它的父节点parent[i].这样，我们先将p,q两点中较深的那个上溯到与另一个相同的深度，然后两者再一层一层共同向上追溯直至它们汇合，这个节点就是它们的LCA。这理论上是o(N)的算法。

有一个log(N)的LCA算法，就是利用binary lifting. 我们先利用parent的信息，预先计算出ancestor[i][j]，表示节点i向上数第2^j层的祖先。这样我们就可以写出时间复杂度是log(n)的getKthAncestor的函数。对于任意的p与q，我们先计算出它们的深度差，用getKthAncestor将较深的那个节点拉至与另一个节点相同。然后用二分搜值，寻找最小的k，使得p与q的getKthAncestor相同，那么这个相同的节点就是它们的LCA。总的时间复杂度仍然是log(n).