Can somebody please give some hints on how to solve this problem . I found one solution which involved lca and range updates on the flattened tree but that didn’t work out. Any help is appreciated @everule1
You can do it in a prefix-sum way with LCA, since queries are “offline”
That is, for each path, increment some counter by 1 for both ends of the path, then decrement the LCA’s counter by 1, then decrement the LCA’s parent’s counter by 1. The final value for each node is the sum of counters in the subtree.
Exact same problem on a different site, for reference: USACO (there’s also an editorial there)
2 Likes
Got it now! thanks for such a prompt response 