Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя Tyler__Durden

Yet Another Tree Problem
Автор Tyler__Durden, история, 6 лет назад, По-английски

I am stuck on this following problem:

Given an undirected tree of n nodes and q queries of type (u,d), for each query you need find the number of simple paths starting from node u and having edge distance <=d.

Constraints:

1<=n,q,u,d<=100000

Any suggestion will be highly appreciated. Thanks.

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

I will assume the edges are unweighted.

Here are some hints:

  • Root the tree arbitrarily.
  • Answer all the queries at once via a DFS and using small-to-large merging (you may also need to keep some auxiliary data structure for each node during your DFS).
  • First figure out how to solve if you want to count nodes with distance from u exactly d. Note that each path for a query has an LCA that is an ancestor of u, and group them by this LCA.
  • Can we adapt this to the version where we want to count nodes with distance at most d?

Total time complexity should be something like or .

Does this help?

→ Ответить