Editorial for DMPG '19 G5 - Hunting the White Whale


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

This problem was greatly inspired by IOI '11 B - Race. Also, Re:Zero season 2 hype!!!

For the first subtask, the tree forms a chain. Thus for each i, we can find the number of indices j such that the sum of all edges between nodes i to j equals K, and add 1 to the nodes i, i+1, \dots, j.

Time Complexity: \mathcal O(N^3)

For the second subtask, we can root the tree at i for i = 1, 2, \dots, N, and then perform a DFS from the root to every other node. If the path from node i to node j has sum K, then we can add 1 to node j.

The update can be achieved by adding 1 to node j, and then propagating this change upwards to the root in a single DFS performed at the end.

Time Complexity: \mathcal O(N^2)

There is no intended solution for subtask 3.

For the final subtask, we can perform centroid decomposition. Consider the tree with centroid C. We want to update all paths with LCA C. We reroot the tree such that C is the root. For every node i in the subtree, let D[i] denote the sum of the t_i values from C to i.

Counting the number of paths of length K that pass through node C is a classical problem. For every other node i \ne C in C's subtree, we can count the number of nodes j that come before i in the Euler tour of the tree such that D[i] + D[j] = K, and \operatorname{LCA}(i, j) = C. Let this number be x. Then we have to add x to the path from C to i. This can be done in constant time.

We then repeat this process, but with a slight modification. For every other node i \ne C in C's subtree, we can count the number of nodes k that come after i in the Euler tour of the tree such that D[i] + D[k] = K, and \operatorname{LCA}(i, k) = C. Let this number be x. Then we have to add x to the path from C to i. This can be done in constant time.

Time Complexity: \mathcal O(N \log N)


Comments

There are no comments at the moment.