Sum of odd valued edges between 2 nodes in a tree with value less than k

Question

I was asked this question by my colleague but i am unable to come up with any optimal solution.
Given an undirected weighted tree with n nodes ,n-1 edges and q queries.
Each query has input u v k , output the sum of edges lying in path u to v with odd value and is less than k .

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

I am struggling to output the query in optimal time i just want to know the approach or method to solve this one(not the code).

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 : Surely there is some precomputation which I am not able to think about.

Answer 1

That depends on what you consider "optimal solution" and what the circumstances are. Given n <= 10, we have a case where even an n^3 process is O(1). I'd simply pre-process the graph with all partial paths and the corresponding list of values (filter for odd, sort the remainder, build a table of partial sums indexed by limit). This makes the query a simple indexed return: table[u, v, limit]. The table for the above graph would look something like below, where * is an arbitrarily large 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]

You can build this table with any complete graph-distance algorithm.

UPDATE AFTER CHANGING UPPER LIMIT OF N

With N <= 10^5, the problem is still O(1), but the overhead is more than we want. Switch to other methods.

I recommend that you change the representation to be an actual tree: directed, with a root. If you want to reduce overall time, find the longest path and take the midpoint as the root node. Otherwise, just grab any node and shake. You can also get decent results by choosing a handful at random and taking the one that yields the least graph height.

While you form your tree, delete any even costs; this will save checking time later.

Now, working with a query is trivial: @Pratik already gave you the algorithm. Note, however, that any non-trivial quantity of queries may make it worthwhile to store partial paths with sorted costs: for instance, each node could carry a reference list of the path weight to each child node, with the weights sorted in descending order.

Answer 2

Since the input is a tree there is going to be only one path between any two nodes. You can use bfs to traverse the tree build path between u and v. Then you filter the edges on the path by < k and odd. Add up the numbers.This takesO(n) time.

EDIT Since there are multiple queries it makes sense to preprocess the tree. Any tree can be rooted. Then you can traverse the tree and update values like as in traverse. You store answer to (root,v) query at each node. This will help you answer any other queries.

'''
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)

The path between any two nodes in a tree must go through their lowest common ancestor (lca). You can can answer queries using following function.

Let lca(u, v) = x.

u.value = x.value + query(x, u) v.value = x.value + query(x, v). We have to take the path u-x-v. So we want query(u,x) + query(x,v) which gives us query function below. To calculate LCA efficiently you have to do another preprocessing step.

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

Looks like after O(n log n) preprocessing you can answer queries in O(log n).