algorithm - 树中 2 个节点之间值小于 k 的奇数边之和

Question

我的同事问了我这个问题，但我无法想出任何最佳解决方案。
给定一棵具有n 个节点、n-1 条边和 q 个查询的无向加权树。
每个查询都有输入 u v k ，输出位于路径 u to v 的奇数且小于 k 的边之和。

1<=n<=10^5
1<=q<=10^5
1<=Weight of edge<=10^8.

我正在努力在最佳时间输出查询我只想知道解决这个问题的方法或方法(不是代码)。

Sample ip for 5 nodes nd 4 edges connected as(u-v-edge weight):
3-5-1 , 1-3-4 , 1-2-1 , 3-4-7
query - 2-4-5 ans=1
query - 2-4-10 ans=8

PS:肯定有一些我无法考虑的预先计算。

Answer 1

由于输入是一棵树，因此任意两个节点之间只有一条路径。您可以使用 bfs to traverse the tree在 u 之间构建路径和 v .然后通过 < k and odd 过滤路径上的边缘.将数字相加。这需要 O(n)时间。

编辑 由于存在多个查询，因此对树进行预处理是有意义的。任何树都可以生根。然后你可以像 traverse 那样遍历树并更新值.您存储 (root,v) 的答案在每个节点查询。这将帮助您回答任何其他问题。

'''
Node 
    - parent
    - children
    - value 
    - name 
'''

def traverse(node):
    for child in node.children:
        if w(node, child) < k and w(node, child) % 2 == 1:
            child.value = node.value + w(node, child)
        traverse(child) 


root.value = 0
traverse(root, 0)

树中任意两个节点之间的路径都必须经过它们的最低共同祖先 (lca)。您可以使用以下功能回答查询。

让lca(u, v) = x .

u.value = x.value + query(x, u) v.value = x.value + query(x, v) .我们必须走这条路 u-x-v .所以我们要 query(u,x) + query(x,v)这给了我们下面的查询功能。要有效地计算 LCA，您必须做 another preprocessing step .

def query(u, v):
    return u.value + v.value - 2 * lca(u, v).value

看起来像在 O(n log n) 之后预处理您可以在 O(log n) 中回答查询.