def bestSumDownwardTreePath(parent: list[int], values: list[int]) -> int:
Given a tree with n nodes, rooted at node 0 (nodes are numbered 0 to n-1), where values[i] is the value of node i, find the maximal sum of values along any path that starts at some node u and goes only down the tree. In other words, only consider paths u1, u2, ..., uk where each node ui is a child of u(i-1) for 1 < i <= k. Values can be positive or negative.
Complete the function bestSumDownwardTreePath. It must return an integer: the largest sum of values along a path down the tree from any node u.
Parameters
parent[0..n-1]: parent[i] is the parent of node i; parent[i] = -1 means node i is the root.values[0..n-1]: values[i] is the value of node i.Example
node / value:
0/5
/ \
1/7 4/15
|
2/-10
|
3/4
parent = [-1, 0, 1, 2, 0]
values = [5, 7, -10, 4, 15]
0 -> 1 -> 2 -> 3 5 + 7 + (-10) + 4 = 6
1 -> 2 -> 3 7 + (-10) + 4 = 1
0 -> 4 5 + 15 = 20 <- the highest
bestSumDownwardTreePath(parent, values) -> 20
Notes
k = 1).n or on the values. Confirm both with the platform's constraints if they are shown.Two candidates reported this as the first of two coding questions in a Citadel online assessment, in March and April 2025.
The April 2025 report (a Citadel / Citadel Securities software engineering campus OA) posts the prompt in English, including the example and the function name bestSumDownwardTreePath(parent, values). The candidate writes that the first question was solved with a DFS. The second question was a graph problem, a friend-recommendation system the candidate compares to LeetCode 1917.
The March 2025 report (a 2025 new-grad OA) describes the same tree question in a sentence: the tree is given as an array, node values can be positive or negative, and the path goes only from parent to child, never back up. It says DFS is the way to solve it. Its second question was a string-matching problem on prefix and suffix scores.
Neither report gives input limits, the time allowed, or the result.
Given a tree with n nodes, rooted at node 0 (nodes are numbered 0 to n-1), where values[i] is the value of node i, find the maximal sum of values along any path that starts at some node u and goes only down the tree. In other words, only consider paths u1, u2, ..., uk where each node ui is a child of u(i-1) for 1 < i <= k. Values can be positive or negative.
Complete the function bestSumDownwardTreePath. It must return an integer: the largest sum of values along a path down the tree from any node u.
Parameters
parent[0..n-1]: parent[i] is the parent of node i; parent[i] = -1 means node i is the root.values[0..n-1]: values[i] is the value of node i.Example
node / value:
0/5
/ \
1/7 4/15
|
2/-10
|
3/4
parent = [-1, 0, 1, 2, 0]
values = [5, 7, -10, 4, 15]
0 -> 1 -> 2 -> 3 5 + 7 + (-10) + 4 = 6
1 -> 2 -> 3 7 + (-10) + 4 = 1
0 -> 4 5 + 15 = 20 <- the highest
bestSumDownwardTreePath(parent, values) -> 20
Notes
k = 1).n or on the values. Confirm both with the platform's constraints if they are shown.What passers do: Solved with a DFS (the April 2025 candidate: the first question was solved with DFS).
Send them this page. It is free to read, no account needed.
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 62 Citadel questions, refreshed monthly from new candidate reports.