Tap here to switch tabs
Problem
Submissions

Problem: Find Number of Coins to Place in Tree Nodes

Find Number of Coins to Place in Tree Nodes asks you to return an array assigning each node one coin when its subtree has fewer than three nodes, or the maximum nonnegative product of three costs otherwise.

Statement

You are given an undirected tree consisting of nn nodes numbered from 00 to n−1n - 1, rooted at node 00. The tree is represented by a 22D integer array edges of length n−1n - 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates an edge between nodes aia_i and bib_i. You are also given a 00 indexed integer array cost of length nn, where cost[i] is the cost associated with node ii.

You need to place coins on each node according to the following rules:

  • If the subtree rooted at node ii contains strictly fewer than 33 nodes, place 11 coin at node ii.

  • Otherwise, select 33 distinct nodes from the subtree rooted at node ii such that the product of their costs is maximized. If this maximum product is negative, place 00 coins at node ii. Otherwise, place coins equal to this maximum product at node ii.

Return an array ans of length nn, where ans[i] is the number of coins placed at node ii.

Constraints:

  • 2≤n≤2⋅1042 \leq n \leq 2 \cdot 10^4

  • edges.length =n−1= n - 1

  • edges[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • cost.length =n= n

  • 1≤∣1 \leq |cost[i]∣≤104| \leq 10^4

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find Number of Coins to Place in Tree Nodes

Find Number of Coins to Place in Tree Nodes asks you to return an array assigning each node one coin when its subtree has fewer than three nodes, or the maximum nonnegative product of three costs otherwise.

Statement

You are given an undirected tree consisting of nn nodes numbered from 00 to n−1n - 1, rooted at node 00. The tree is represented by a 22D integer array edges of length n−1n - 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates an edge between nodes aia_i and bib_i. You are also given a 00 indexed integer array cost of length nn, where cost[i] is the cost associated with node ii.

You need to place coins on each node according to the following rules:

  • If the subtree rooted at node ii contains strictly fewer than 33 nodes, place 11 coin at node ii.

  • Otherwise, select 33 distinct nodes from the subtree rooted at node ii such that the product of their costs is maximized. If this maximum product is negative, place 00 coins at node ii. Otherwise, place coins equal to this maximum product at node ii.

Return an array ans of length nn, where ans[i] is the number of coins placed at node ii.

Constraints:

  • 2≤n≤2⋅1042 \leq n \leq 2 \cdot 10^4

  • edges.length =n−1= n - 1

  • edges[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • cost.length =n= n

  • 1≤∣1 \leq |cost[i]∣≤104| \leq 10^4

  • The input is generated such that edges represents a valid tree.