1. bestSumDownwardTreePath

Problem

Given a tree with n nodes rooted at node 0 (nodes are numbered from 0 to n-1), and a list of integer values for each node, find the maximal sum of values along any downward path starting from any node u. A downward path is a path where each node is a child of the previous one in the path.

Function Signature

def bestSumDownwardTreePath(parent: List[int], values: List[int]) -> int:

Input

• parent: List of integers of length n, where parent[i] denotes the parent of node i, and parent[i] == -1 indicates that node i is the root.
• values: List of integers of length n, where values[i] is the value assigned to node i.

Output

• Returns an integer: the maximum sum of any path starting from some node and going down the tree.

Example

Tree representation with nodes labeled as node/value:

0/5
├── 1/7
│   └── 2/-10
│       └── 3/4
└── 4/15

Possible downward paths and their sums:

• 0 → 1 → 2 → 3: sum = 5 + 7 + (-10) + 4 = 6
• 1 → 2 → 3: sum = 7 + (-10) + 4 = 1
• 0 → 4: sum = 5 + 15 = 20 (maximum)

Constraints

• 1 ≤ n ≤ 10^5
• -10^4 ≤ values[i] ≤ 10^4
• The input tree is valid and connected.

---

2. getRecommendedFriends

Problem

Implement a friend recommendation system. There are n users indexed from 0 to n-1 and m friendships represented as a list of pairs. A user x is suggested as a friend to user y if:

1. x and y are not already friends.
2. x and y have the maximum number of mutual friends.
3. If multiple users satisfy the above, choose the one with the smallest index.

Function Signature

def getRecommendedFriends(n: int, friendships: List[List[int]]) -> List[int]:

Input

• n: Integer representing number of users.
• friendships: List of pairs where each friendships[i] = [a, b] indicates that user a and user b are friends.

Output

• Returns a list of n integers. The i-th integer is the index of the recommended friend for user i. If no recommendation is available, return -1 for that user.

Example

n = 5
friendships = [
    [0, 1],
    [0, 2],
    [1, 3],
    [2, 3],
    [3, 4]
]

The recommended friends for each user are:

[3, 2, 1, 0, -1]

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.