I just encountered a difficult problem with no solution. Can someone help me, thanks in advance.
Given a tree with N vertices. There are Q queries, the ith query is represented by K pairs (v, r), all vertices whose distance from v is not more than r will be marked. Ask how many vertices are marked per query. Limit N <= 5e4, Q <= 5e5 + N, the total K of all queries does not exceed 5e5 + N.
Auto comment: topic has been updated by sadboi2009 (previous revision, new revision, compare).
I think this problem might be helpful: https://judge.yosupo.jp/problem/vertex_get_range_contour_add_on_tree
Do you have solution this problem
The main idea is centroid decomposition. For further details you can look at AC submissions to this problem.
i think 2 problem can solve by centroid but i don't know how :))
Centroid decomposition
How do you do :))
Are queries independent?
yes
Hint: Centroid decomposition. For every ancestor of node in centroid tree, count vertices with appropriate distance. Sort of like the famous problem Xenia and Tree
How do you deal with duplicate counts?