HackerRank Coding Interview 9. Rooted Distances — Part 1 — Question

Recommended Time: 45 mins

Skills:Problem Solving (Advanced)

Coding- HARD, Trees, Dynamic Programming

Languages: Python

Problem statement

Given a tree of tree_nodes vertices labeled from 1 to tree_nodes, each vertex is associated with a value a[i] . We define the beauty of some vertex v (where 1 ≤ v ≤ tree_nodes) as the sum of dis(i, v) * a[i] over all vertices i (where 1 ≤ i ≤ tree_nodes). Here dis(i, v) denotes the number of edges on a simple path from i to v.

Determine the maximum value of beauty for any vertex v.

Example

tree_nodes = 2

tree_edges = 1

tree_from = [1]

tree_to = [2]

a = [3, 4]

For vertex 1, beauty is dis(1, 1) * 3 + dis(2, 1)*4 = 0*3 + 1*4 = 4.

For vertex 2, beauty is 1*3 + 0*4 = 3.

It is optimal to choose vertex 1 with a beauty of 4.

Function Description

Complete the function maxBeauty in the editor below.