sadboi2009's blog

A hard tree problem, hope someone can help me, Thanks
By sadboi2009, history, 10 days 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

»
10 days 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
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this problem might be helpful: https://judge.yosupo.jp/problem/vertex_get_range_contour_add_on_tree

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you have solution this problem

    → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The main idea is centroid decomposition. For further details you can look at AC submissions to this problem.

      → Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think 2 problem can solve by centroid but i don't know how :))

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Centroid decomposition

→ Reply
»
10 days 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