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

Автор sak3t, история, 6 лет назад, По-английски

Given a weighted tree of $$$N <= 10^5$$$ nodes, answer $$$Q <= 10^5$$$ queries.
Each query will have $$$node, k$$$ asking number of all the nodes having even weight in the subtree of $$$node$$$ and at a distance $$$k$$$ from $$$node$$$.
Please provide hints.

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

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

who have weight nodes or edges ? where is the problem ?

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

This problem can be solved offline with a tree technique called DSU on tree

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

You can do a DFS, maintaining in time and out time. Also maintain a list of nodes for each level in the order in which they appear during the DFS. Each query is finding number of weights in level (k + lev[node]) with DFS in-time in the range [in[node], out[node]]. This can be done in O(logn) using Binary search.

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

If that is another simpler solution since you only need to have the time of entry of each node in the DFS and the time of exit. But my idea is: since the solution for an X node is going to depend on the solution for all the nodes adjacent to X that are not its father, of course, and the nodes that are at a distance K from the X node are the same to say the number of nodes that meet the condition of parity at a depth = lv (x) + k we can take a map for example to keep the solution for a depth Y in the X subtree. Then we only need to join the solution of all the nodes adjacent to X as the solution of X and since the problem can be done offline we can find all the solutions as we calculate the solutions for each node.

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

I think it's about dsu on tree https://mirror.codeforces.com/blog/entry/44351

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

If you have to answer queries online then this can be done using persistent segment tree also with time complexity(Q*log(N) + N*log(N).