## Editorial for UTS Open '18 P7 - Gossip Network

**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:

##### 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