coinbase

Problem Statement

Restaurant Chain A restaurant chain runs N restaurants, numbered 0 to N-1 . The head office is restaurant 0 . The chain publishes a list of N-1 connections; each connection joins two restaurants, and along these connections there is exactly one route between any two restaurants. This makes the chain a hierarchy headed by restaurant 0 . For any restaurant X other than 0 , its superior is the restaurant next to it on the unique route from X to the head office; every other restaurant directly connected to X is a subordinate of X . No restaurant has more than two subordinates. Each restaurant has a recorded number of permanent customers. To choose a restaurant to host the annual festival, the chain builds a sequence of restaurant IDs. Each restaurant with two subordinates calls the one whose connection appears earlier in the connection list its left subordinate and the other its right subordinate; a restaurant with exactly one subordinate calls it its left subordinate. The sequence is then