### sak3t's blog

By sak3t, history, 9 months ago, ,

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

• 0

 » 9 months ago, # |   0 who have weight nodes or edges ? where is the problem ?
•  » » 9 months ago, # ^ |   0 Weights are on nodes.Problem is how to compute queries.
 » 9 months ago, # |   0 This problem can be solved offline with a tree technique called DSU on tree
•  » » 9 months ago, # ^ |   0 Can you please briefly explain how it would work?
 » 9 months ago, # |   +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.
 » 9 months ago, # |   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.
 » 9 months ago, # |   0 I think it's about dsu on tree https://codeforces.com/blog/entry/44351
 » 9 months ago, # |   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).