sak3t's blog

How to solve this tree problem?
By sak3t, history, 6 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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

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

    Weights are on nodes.
    Problem is how to compute queries.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Can you please briefly explain how it would work?

    → Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply