Editorial for UTS Open '18 P7 - Gossip Network
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Each time a piece of news is announced, perform a DFS to update the total interest value heard by each person. This allows you to answer type-2 queries in .
Time Complexity:
Subtask 2
Use a BIT-like data structure, where left[] is the sum of the interest values heard by student
for any news originating from the
students to the left of
, where
denotes the largest power of
dividing
(this is
i&-i in C++). Construct a second BIT with right instead of left, then we can update and query in time.
Time Complexity:
Subtask 3
Perform centroid decomposition on the tree. For each student, store the sum of the interest values of any news they heard that originated from a descendant in the centroid tree. This takes per type-1 query, since news starting at
only requires updating the ancestors of
in the centroid tree (there are at most
ancestors, and the product of popularities along a path can be calculated in
using LCA's. Type-2 queries can be answered in
, by adding up the stored sum of products (multiplied by the product of popularities on the path to
) for all ancestors of
in the centroid tree, and subtracting any products that were counted multiple times.
Time Complexity:
Comments
Queries are solvable in
time by storing additional information in your centroid decomposition:
Centroid -> Amount of interest attained from each subtree
Children of centroid -> Total product in the path to the centroid, index of the subtree that the node is in