The Sack algorithm allows responding offline queries related to node subtree information in a tree. A concept introduced in the algorithm is that of heavy son, in which the heavier nodes inherit their information to the parent (causing the heavy part of the processing to be discarded) and the lighter ones are processed normally. Some problems that can be solved with the Sack algorithm:
- Lomsat gelral - Codeforces
- Tree Requests - Codeforces
- Coloring Tree - HackerRank
- Hedwig The Smart Bird - Codechef
- Summing in a tree - HackerRank
- Treedif - VJudge
Troubleshooting the above using sack: