Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

sadboi2009's blog

A hard tree problem, hope someone can help me, Thanks
By sadboi2009, history, 2 months ago, In English

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.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sadboi2009 (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Centroid decomposition

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

→ Reply