Editorial for UTS Open '18 P7 - Gossip Network

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: PlasmaVortex

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 \mathcal{O}(1).

Time Complexity: \mathcal{O}(NQ)

Subtask 2

Use a BIT-like data structure, where left[i] is the sum of the interest values heard by student i for any news originating from the f(i) students to the left of i, where f(i) denotes the largest power of 2 dividing i (this is i&-i in C++). Construct a second BIT with right instead of left, then we can update and query in \mathcal{O}(\log N) time.

Time Complexity: \mathcal{O}(Q \log N + N)

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 \mathcal{O}(\log^2 N) per type-1 query, since news starting at s only requires updating the ancestors of s in the centroid tree (there are at most \mathcal{O}(\log N) ancestors, and the product of popularities along a path can be calculated in \mathcal{O}(\log N) using LCA's. Type-2 queries can be answered in \mathcal{O}(\log^2 N), by adding up the stored sum of products (multiplied by the product of popularities on the path to s) for all ancestors of s in the centroid tree, and subtracting any products that were counted multiple times.

Time Complexity: \mathcal{O}(N \log N + Q \log^2 N)


  • 0
    kuruluu  commented on May 30, 2024, 3:35 a.m.

    Queries are solvable in \mathcal{O}(\log N) 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