Track Customer Referral Revenue

Problem Statement

You are building a referral tracking system for a ride-sharing platform. Each user has a unique user_id and is invited by exactly one referrer_id (except for the original founders who have None). Every user generates a certain amount of revenue from their own rides.

A user's 'total contributed revenue' is the sum of their own revenue plus the total contributed revenue of all users in their entire referral subtree.

Design a class ReferralTracker that manages these relationships and provides a way to identify users who contribute less than a specific amount of total revenue.

Class Interface

class ReferralTracker:
    def __init__(self, users: list[tuple[int, int, int | None]]):
        # users is a list of (user_id, revenue, referrer_id)
        pass

    def get_subtree_revenue(self, user_id: int) -> int:
        # Returns the total contributed revenue for the given user
        pass

    def find_users_below_threshold(self, threshold: int) -> list[int]:
        # Returns a list of user_ids whose total contributed revenue < threshold
        pass

Constraints

• Number of users: up to 10^5.
• revenue is a non-negative integer.
• The referral structure is guaranteed to be a valid forest (a collection of trees).

Example

Input:

• Users: [(1, 10, None), (2, 5, 1), (3, 2, 1), (4, 1, 2)]
• 1 refers 2 and 3; 2 refers 4.
• Revenues: 1:10, 2:5, 3:2, 4:1

Calculations:

• Subtree 4: 1
• Subtree 2: 5 + 1 = 6
• Subtree 3: 2
• Subtree 1: 10 + 6 + 2 = 18

get_subtree_revenue(2) returns 6. find_users_below_threshold(5) returns [3, 4].