Traffic Control Hubs

Problem Statement

Traffic Control Hubs Problem Description A smart city has an infinite number of traffic control hubs, numbered with the positive integers 1, 2, 3, ... . The hubs are joined by bidirectional smart roads: there is a road between hub i and hub 2 * i , for every i >= 1 ; there is a road between hub i and hub 2 * i + 1 , for every i >= 1 . There are no other roads. With this layout there is exactly one shortest route between any two hubs, and every commuter always uses it. (inferred -- the source's first rule reads "between hub 1 and 2i"; that is a transcription slip for "between hub i and 2i", which the source's own example outputs confirm.) Initially every road is toll-free. The traffic authority then processes q events, one after another, in the order given: Toll fee update 1 x y t : the toll of every road on the shortest route between hub x and hub y is increased by t units. Tolls accumulate: a road named by several updates carries the sum of all amounts added to it. Travel cost c