algorithm - 树的每对顶点之间的最大流量之和

Question

给定一棵无向树，其中 N 个顶点编号从 1 到 N。每棵边树都有一定的容量。找到所有可能的顶点对之间的最大流量之和。任意两个顶点之间只存在一种方式。
找到所有可能的顶点对之间的最大流量之和。

例如:在给定的有 3 条边的树中
1 2 5
2 3 6
节点 1 和节点 2 之间的边容量为 5，节点 2 和节点 3 之间的边容量为 6。
输出 - 32

(1,2) = (2,1) = 5
(1,3) = (3,1) = 5
(2,3) = (3,2) = 6
因此输出为 (5+5+6)*2 = 32

我的方法-

1. 排序基于edge_capacity的边

2. 当edge_list不为空时:删除容量最小的边

   • 计算这条边的左边和右边上的节点数。为节点计数做 DFS
   • 将 (left_count * right_count * edge_capacity) 添加到答案中。

3. 返回答案*2。
   

时间复杂度为 O(n²)。此解决方案提供 TLE。
如何进一步降低时间复杂度？

我的代码-

def dfs(node):
    count = 1
    visited = set()
    stack = [node]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(set(nodes[vertex]) - visited)
    return len(visited)

for _ in range(int(raw_input())):   # Iterate for multiple test cases
    MOD = 1000000007
    edges = []
    n = int(raw_input())            # number of vertices
    nodes = [set() for _ in range(n)]
    for __ in range(n-1):           # read input for number of edges
        edges.append(map(int, raw_input().split()))
        nodes[edges[-1][0]-1].add(edges[-1][1]-1)    
        nodes[edges[-1][1]-1].add(edges[-1][0]-1)
        edges[-1][0]-=1; edges[-1][1]-=1; 
    edges.sort(key=lambda x: x[2])

    answer = 0
    for i in range(len(edges)):
        weight = edges[i][2]
        x, y = edges[i][0], edges[i][1]
        nodes[x].remove(y)
        nodes[y].remove(x)
        left_count = dfs(x)
        right_count = dfs(y)
        answer += ((left_count*right_count*weight)%MOD)
    print (answer*2)%MOD

链接到原始问题- Spoj-Flow on Tree

更新

约束-

1. 测试用例数量 - 10
2. 1 <= N <= 10⁵(每个测试用例中的顶点数)
3. 每条边的容量为非负且不超过 10⁶。
4. 所有测试用例的顶点总数将小于 5*10⁵。

Answer 1

与其每次都运行两个新的 DFS 来计算子树的大小，不如运行一次更智能的 DFS，它为每条边 uv 计算删除边 uv 时形成的以 u 为根的子树中的节点数。 (请注意，您需要为 uv 和 vu 计算此值。)

有关以线性时间计算这些节点数的方法，请参阅 this nice answer .