Tap here to switch tabs
Problem
Submissions

Problem: Find Number of Coins to Place in Tree Nodes

Try to solve the Find Number of Coins to Place in Tree Nodes problem.

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

Try to solve the Find Number of Coins to Place in Tree Nodes problem.

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.