Editorial for UTS Open '18 P7 - Gossip Network - Olympiads Online Judge

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)$ $O (1)$ .

Time Complexity: $\mathcal{O}(NQ)$ $O (N Q)$

Subtask 2

Use a BIT-like data structure, where left[ $i$ $i$ ] is the sum of the interest values heard by student $i$ $i$ for any news originating from the $f(i)$ $f (i)$ students to the left of $i$ $i$ , where $f(i)$ $f (i)$ denotes the largest power of $2$ $2$ dividing $i$ $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)$ $O (\log N)$ time.

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

Comments

0

kuruluu commented on May 30, 2024, 3:35 a.m. ← edited →

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