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)~