Asynchronous Distributed Tree Count Aggregation

Problem: Asynchronous Distributed Tree Count Aggregation Each node of a tree is an independent process in a network. A node has no global view of the tree and can communicate only with its direct parent and direct children. Sending is asynchronous and non-blocking: sendAsync(toNode, message) Design and implement a Node class and its message-handling logic so that the root can initiate a count request and eventually obtain the total number of nodes in its subtree. Each node should maintain at least: id parent children Local state for one count request Your implementation must handle two message types: GET_COUNT: asks a node to count the nodes in its subtree. REPORT_COUNT: reports a child subtree's count to its parent. Implement: receive(fromNode, message) Required behavior: When the root initiates or receives GET_COUNT, it asynchronously sends GET_COUNT to every direct child. A non-leaf node receiving GET_COUNT forwards it to all of its children and waits for their reports. A leaf receiving GET_COUNT immediately sends REPORT_COUNT(1) to its parent. Upon receiving a child's REPORT_COUNT, a node accumulates the reported value and records that the child has reported. Once a node has received reports from all direct children, it sends this value to its parent: 1 + sum(all child reports) Once the root has collected all child reports, it outputs the final count. Do not use synchronous waiting, a shared global counter, or a centralized traversal of the tree. Nodes must coordinate exclusively through messages. Local simulation input format For testing, simulate a reliable, asynchronous, exactly-once network with an event queue. n root p0 p1 ... p(n-1) n is the number of nodes, numbered from 0 through n - 1. root is the root node ID. pi is the parent ID of node i; the root has parent -1. The input is guaranteed to form a tree rooted at root. Print the final count obtained by the root. Constraints 1 <= n <= 200000 In the base problem, delivery is reliable and exactly once. Messages may arrive in any order. Example 1 Input: 5 0 -1 0 0 1 1 Output: 5 Example 2 Input: 1 0 -1 Output: 1 Follow-up: Unreliable network How would you modify the protocol if messages may be lost or delivered more than once? Explain how you would handle: Duplicate GET_COUNT requests; Duplicate REPORT_COUNT messages; Lost requests or reports; Multiple concurrent count requests. Example Input 1 0 -1 Output 1