Distance Sums to Special Nodes in a Weighted Tree
Updated
Problem statement
You are given a tree with n nodes labeled from 1 to n. Each edges[i] = [a, b, w] is an undirected edge of length w between node a and node b. The distance dist(u, v) is the total length of the edges on the path from u to v, and dist(u, u) = 0.
Part 1. Find the total distance from node x to all nodes, that is, the sum of dist(x, v) over every node v.
Part 2. You are also given special, a list of different nodes. The value of a node v is the sum of dist(s, v) over every node s in special. Find the smallest value any node has, and the node that has it. If several nodes share the smallest value, pick the one with the smallest label. Part 2 does not use x, and the best node does not have to be special.
Return the array [sum, node, value]: the Part 1 sum, then the Part 2 node and its value.
Function
specialNodeDistances(n: int, edges: int[][], x: int, special: int[]) → long[]Examples
Example 1
n = 5edges = [[1,2,4],[2,3,1],[2,4,2],[4,5,3]]x = 1special = [3,5]return = [24,2,6]Part 1: from node 1, the distances are 0 to node 1, 4 to node 2, 4 + 1 = 5 to node 3, 4 + 2 = 6 to node 4 and 6 + 3 = 9 to node 5. They add up to 24.
Part 2: the special nodes are 3 and 5, and the path between them is 3, 2, 4, 5 with length 1 + 2 + 3 = 6. Every node on that path is at distance 6 in total from the two special nodes, so nodes 2, 3, 4 and 5 all have a value of 6. Node 1 is off the path: it is 5 from node 3 and 9 from node 5, so its value is 14. The smallest value is 6, and the smallest label that reaches it is 2.
Example 2
n = 6edges = [[1,2,5],[1,3,5],[1,4,5],[4,5,1],[4,6,1]]x = 4special = [2,3,5]return = [27,1,16]Part 1: from node 4, node 1 is 5 away, nodes 2 and 3 are 10 away, and nodes 5 and 6 are 1 away, so the sum is 5 + 10 + 10 + 1 + 1 = 27. Node 4 does not have to be special.
Part 2: the special nodes are 2, 3 and 5. Node 1 is 5 from node 2, 5 from node 3 and 6 from node 5, for a value of 16. Node 4 has 10 + 10 + 1 = 21, nodes 2 and 3 each have 0 + 10 + 11 = 21, node 5 has 11 + 11 + 0 = 22 and node 6 has 11 + 11 + 2 = 24. The best node is 1 with value 16, even though it is not special.
Example 3
n = 1edges = []x = 1special = [1]return = [0,1,0]There is only one node. Its distance to itself is 0, so both the Part 1 sum and the smallest value are 0, at node 1.
Constraints
1 <= n <= 10^4edges.length == n - 1edges[i].length == 31 <= edges[i][0], edges[i][1] <= n1 <= edges[i][2] <= 10^6- The edges form a tree: every node can reach every other node.
1 <= x <= n1 <= special.length <= n1 <= special[j] <= n- All values in
specialare different.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
- Tree Node With Maximum BeautyC3.ai · OAC3.ai interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Transitive Employee Referral CountsRobinhood · ONSITE INTERVIEWRobinhood interview questions
- Aggregate Machine TopologyOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Diameter of an Acyclic Undirected GraphSalesforce · ONSITE INTERVIEWSalesforce interview questions