CODEWITHSUNDEEP
algorithmdata-structuresgraph
imagin
imagin

Reputation: 317

weight sum for path between two nodes in a tree

You are given a Tree with n vertices. Every node has an integer weight associated with it. There are a huge number of queries(~n^2) on the given tree. for a query (A, B), where A, B are two vertices of the tree, you need to calculate sum of weights of the nodes on the unique path from A to B, including A and B.

I can do dfs/bfs for individual queries but that is going to take O(n^3) for ~n^2 possible queries.. can anyone suggest something better which takes less than O(n) per query?

thanks..

Upvotes: 4

Views: 4108

Answers (2)

Fallen
Fallen

Reputation: 4565

If the tree is not rooted, make any arbitrary node the root of the tree.

We'll denote weight of the node x with W[x] and sum of weights of all nodes from root to node x with C[x].

Now let's assume there's a query like, u, v:

We've to find the Lowest Common Ancestor of node u and v. Let's assume the LCA of u and v is P. so the result for query (u,v) will be C[u]-C[P]+C[v]-C[P]+W[P]

Upvotes: 3

panhantao
panhantao

Reputation: 11

Isn't your problem very similar to Timus Online Judge 1471.Tree ? The only difference is that nodes are weighted in your problem while edges are weighted in Ural 1471.Tree.

This is a typical LCA problem.

Make anyone of the nodes as the root of the tree(if necessary), then calculate the distance dist[i] of every other nodes to the root, which takes O(N) time using BFS/DFS. Then for each query(A,B), find the LCA L of (A,B), then the distance between of (A,B) is dist[A] + dist[B] - 2*dist[L].

However, in your problem, it may be necessary to convert the node weight to edge weight.

If you are not familiar with the LCA algorithm, here is a very good site that may help you.

Upvotes: 1

Related Questions