Daily challenge for 2026-10-28
666. Subtree Supply Overflow Nodes
You are given a rooted tree with n nodes labeled from 0 to n - 1, rooted at node 0. The structure of the tree is represented by an array parent of size n, where parent[i] is the parent of node i, and parent[0] = -1.
You are also given an array supplies of length n, where supplies[i] is the non-negative supply stored at node i, and an integer limit.
The subtree supply of node i is defined as the sum of supplies of all nodes in the subtree rooted at i (including node i itself).
Return the number of nodes whose subtree supply is strictly greater than limit.
Constraints:
The parent array represents a valid connected rooted tree of 1–500 nodes with root 0 and parent[0] = -1. Every other node has one valid parent, with no cycles. Supplies has the same length and contains non-negative integers at most 1,000,000. The limit is an integer with absolute value at most 1,000,000,000; equality does not exceed it.
Example:
Input: parent = [-1, 0, 0, 1], supplies = [2, 3, 5, 4], limit = 6
Output: 2