Serialize Cluster Topology

Instructions

A cluster of machines is wired as a rooted n-ary tree. Each machine has a unique integer id from 0 to n - 1 and knows only two things about the cluster: its parent's id (-1 if it is the root) and the ids of its immediate children. No machine can see the tree as a whole.

Machines talk to each other through a provided messaging API:

class Channel:
    def send(self, from_id: int, to_id: int, message: str) -> None:
        # queues a message; it is delivered later by calling
        # handle_message(from_id, message) on the target machine

Three rules govern messaging:

• Neighbors only. A machine may send to its parent or one of its children. Anything else is an error. The object you are given exposes send and nothing else — there is no tree to read and no other machine's state to inspect.
• Delivery is asynchronous. send returns immediately, and queued messages are delivered in arbitrary order. When you fan a request out to several children, their replies can come back in any order, so each machine must remember what it is still waiting for.
• The client is id -1. It starts an operation by sending a request to the root; the root answers by sending the finished result back to CLIENT_ID. Exactly one answer per operation reaches the client.

Support two operations:

1. "count" — the total number of machines in the cluster, as a string. A machine sums the counts reported by its children, adds 1 for itself, and passes the total up. Leaves report 1.
2. "topology" — a string describing the tree's shape, assembled from the leaves upward. A leaf serializes as "<id>". A machine with children serializes as "<id>(<c1>,<c2>,...)", where each c is a child's own serialization and children appear in ascending id order — not the order their replies happened to arrive.

Example 1:

0
├── 1
└── 2
    └── 3

count    -> "4"
topology -> "0(1,2(3))"

Explanation: Machines 1 and 3 are leaves, so they answer immediately. Machine 2 waits for 3 before it can report "2(3)", and the root waits for both 1 and 2.

Example 2:

0

count    -> "1"
topology -> "0"

Explanation: The root is also a leaf. It answers without sending a single request.

Example 3:

0
├── 1
├── 2
├── 3
└── 4

count    -> "5"
topology -> "0(1,2,3,4)"

Explanation: All four children are leaves and reply in whatever order the channel delivers them, but the root must still list them as 1,2,3,4.

Example 4:

0
├── 1
│   ├── 3
│   └── 4
│       └── 5
└── 2
    └── 6

count    -> "7"
topology -> "0(1(3,4(5)),2(6))"

Explanation: Serializations nest. Machine 4 reports "4(5)", so machine 1 reports "1(3,4(5))", which the root embeds in turn.

Constraints:

• 1 <= n <= 10^4
• A machine may only message its parent or its children, and may not inspect the tree.
• Replies from different children interleave arbitrarily.
• Both operations may be in flight at once, so tag messages with an operation id — a machine must keep concurrent operations' partial results apart.
• Use at most 2 messages per tree edge per operation: one request down, one reply up.

Function Signature

Result will appear here after submission.