由n-1边连接的树形n顶点。。然后我必须根据查询找到从(a到b边缘(的总成本。每条边都有特定的成本。我正在尝试使用dfs。但我变老了。有更好的方法。
请提出一些更好的方法。特别感谢他们！
任意根目录树，并预先计算从根到每个节点的距离。然后，对于每个查询(a,b)，计算a和b的最低公共祖先(称之为c(，然后两者之间的距离将为(dist[i]表示距根的距离(dist[a]+dist[b]-2*dist[c]。在O(N)中运行距离预计算，在O(NlogN)中运行LCA预计算，并且每个单独的查询都可以在O(logN)中运行(取决于实现(。
网上有很多关于这个问题的资源，所以如果我链接的Hackerrank页面不够，请随时在谷歌上搜索更多。