All geek questions in one place

Weighted amount for the path between two nodes in the tree

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

I can do dfs / bfs for individual requests, but it will take O (n ^ 3) for ~ n ^ 2 possible requests. can anyone suggest something better that takes less than O (n) for each request?

thanks..

+4
source share
2 answers

If the tree is not embedded, make an arbitrary node the root of the tree.

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

Now suppose there is a query like u, v :

We need to find the junior common ancestor node u and v. Assume that LCA u and v are P., so the result for the query (u, v) is C[u]-C[P]+C[v]-C[P]+W[P]

+3
source

Isn't your problem very similar to Timus Online Judge 1471.Tree ? The only difference is that the nodes are weighed in your task, and the edges are weighed in Ural 1471.Tree.

This is a typical LCA problem.

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

However, in your problem, you may need to convert the weight of the node to the weight of the edge.

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

+1
source

Source: https://habr.com/ru/post/1494422/

More articles:


All Articles