Tyler__Durden's blog

Yet Another Tree Problem
By Tyler__Durden, history, 6 years ago, In English

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.

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

»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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?

→ Reply