我们得到一个带N (up to 100,000)节点的树.每个边缘被加权任一+1或-1和节点从编号1到N.(A, B)存在多少无序对,使得在路径上A -> X -> B,其中X(X != A && X != B)是路径之间的某些顶点A和B,路径上的边权重之和A -> X是,0并且路径上边缘权重的总和X -> B是0？
因此,我们只关心偶数路径长度,否则边缘权重的总和不能0.我们不能重复对潜在A和B,否则我们得到一个O(N^2)解决方案,这将不低于1秒运行.有关如何解决的任何提示？该程序应该在1秒内运行,因此一个O(N)或一个O(N logN)解决方案可以工作.
编辑:但是,如果我们可以计算从每个节点开始的良好路径的数量,我们就能够解决问题.有可能计算出来吗？听起来对我而言,但我不确定.