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

Question

我的同事问我这个问题，但我想不出任何最佳的解决办法。

给定一个无向加权树，具有n个节点，n-1边和Q查询.

每个查询都输入u v k，输出路径u到v中的边之和，具有奇数值，且小于k。

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

我很难在最优时间输出查询，我只想知道解决这个问题的方法或方法(不是代码)。

5节点和4条边连接为(u-v-边权)的ip样本: 3-5-1，1-3-4，1-2-1，3-4-7 查询- 2-4-5 ans=1查询- 2-4-10 ans=8

PS :当然有一些我无法考虑的预计算。

Answer 1

这取决于你认为什么是“最佳解决方案”以及具体情况。给定n个<= 10，即使n^3过程也是O(1)。我只需预处理包含所有部分路径和相应的值列表的图(对奇数进行筛选，排序余数，构建一个由极限索引的部分和组成的表)。这使得查询成为一个简单的索引返回: tableu，v，limit。上面图的表如下所示，其中*是任意大的限制。

1 2 [*: 1]
1 3 [*: 0]
1 4 [6: 0, *: 7]
1 5 [*: 1]
2 3 [*: 1]
2 4 [6: 1, *: 7]
2 5 [*: 2]
3 4 [6: 0, *: 7]
3 5 [*: 1]
4 5 [6: 1, *: 7]

您可以使用任何完整的图距离算法构建此表。

更改N个上限后的更新

对于N <= 10^5，问题仍然是O(1)，但是开销比我们想要的要多。切换到其他方法。

我建议您将表示更改为实际的树:定向的，有根的。如果要减少整个时间，请找到最长的路径，并以中点作为根节点。否则，只要抓住任何节点并摇晃即可。你也可以得到不错的结果，通过随机选择少数，并采取一个，产生最小的图形高度。

当您形成树时，删除任何偶数成本；这将节省稍后的检查时间。

现在，处理查询非常简单：@Pratik已经给出了算法。但是，请注意，任何重要的查询量都可能使存储部分路径具有排序成本是值得的:例如，每个节点可以为每个子节点携带路径权重的引用列表，权重按降序排序。

Answer 2

因为输入是一棵树，所以在任意两个节点之间只有一条路径。您可以在bfs遍历树和v之间使用v构建路径。然后通过< k and odd过滤路径上的边缘。将numbers.This加起来需要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，您必须执行另一个预处理步骤。

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

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