给出一个邻接图和几个遍历图求出最遍历边的优化方法

Question

给出了一棵树的N个顶点及其相应的邻接图，由N个数组，adjGraph[N][N]表示为一个N。例如，如果(1,3)是边，那么adjGraph[0][2] == 1。否则，(i，j)s不是边的adjGraph[i][j] == 0。

我得到了一系列的投入，形式如下：

1 5

它表示从顶点1到顶点5已经遍历了一条路径。我希望找到遍历次数最多的边，以及它被遍历的次数。为此，我有另一个N乘N数组，numPass[N][N]，它的元素首先初始化为0，然后每次识别包含与其索引匹配的边的路径时增加1。例如，如果路径(2,4)包含边(2,3)和(3,4)，我将分别增加numPass[1][2]和numPass[2][3] 1。

据我所知，要解决的主要问题是输入只给出起始顶点和结束顶点的信息，这取决于我自己来找出这两条边的连接点。由于给定的图是一棵树，两个顶点之间的任何路径都是唯一的。因此，我假设给定任何输入路径的结束顶点的索引，我将能够递归地回溯哪些边是连接的。

下面是我为实现这个想法而尝试实现的函数代码：

// find the (unique) path of edges from vertices x to y
// and increment edges crossed during such a path
void findPath(int x, int y, int N, int adjGraph[][N], int numPass[][N]) {
int temp;

// if the path is a single edge, case is trivial
if (adjGraph[x][y] == 1) {
    numPass[x][y] += 1;
    return;
}

// otherwise, find path by backtracking from y
backtrack: while (1) {
    temp = y-1;
    if (adjGraph[temp][y] == 1) {
        numPass[temp][y] += 1;
        break;
    }
}
if (adjGraph[x][temp] == 1) {
    numPass[x][temp] += 1;
    return;
} else {
    y = temp;
    goto backtrack;
}

但是，问题是，虽然我的代码对于小输入很好，但对于大型输入却没有内存，因为我需要的内存限制为128 my，时间限制为1秒。输入的范围可达222222个顶点和222222个输入路径。

我怎么能优化我的方法来满足这么大的输入？

Answer 1

1. 去掉邻接矩阵(它使用O(N^2)空间)。使用邻接列表代替。
2. 使用更有效的算法。让这棵树生根吧。对于从a到b的路径，我们可以将1添加到a和b中，并从它们的lca中减去1(很容易看出，这种方式将1添加到该路径的边缘，并且只添加到它们)。
3. 在处理完所有路径后，通过边缘的路径数只是子树中的一个和。

如果我们使用一种有效的算法来计算lca，这个解决方案可以在O(N + Q * log N)中工作，其中Q是路径数。对于这些约束，它看起来足够好(实际上，我们可以使用更复杂和更有效的算法来查找lca，但我认为这里没有必要)。

注: lca是指最低的共同祖先。