The task is to find the number of kth-descendants of vertex v. I'm given the full tree of size n,n-1 vertices and q queries with the v and k. What is the fastest way to find the answer? I believe the solution is O(N * log N),because max N,Q is = 500 000 and time limit is 2 sec. Here is example of input:
4
1 2
2 3
1 4
3
1 1
1 2
3 1
And output is:
2 1 0
I've tried using binary-lifting and LCA to find it, and I came up with idea to search at the depth of k + v.depth, and find such L and R that LCA(L,R) = v but it seems not to work properly.
//edit i've tried using binary-search to find min L and max R at depth k+ v.depth that LCA(L,R) = v
n is the number of vertices in a tree, n-1 is the number of edges between vertices(in input after n there is a and b and it means that in the tree there is a edge between vertex a and b), next we have a q which means a number of queries. In each query there is v and k,which stands for a vertex v for which we need to find answer and k is the level of descendant we are looking for. For example if k = 1 we are looking for a descendant of v, if k = 2 we are looking for 2-descendant of v(basically descendants descendant)(its hard to explain but its like our sons son = grandson). Here is the whole code that i've tried. At some point my code outputs 0 instead of 2 and i'm not sure at which case. https://gist.github.com/statkiewiczm/d3826bf8e4cd72ef5d7fb690d981ef5e //final edit I've solved the problem. The solution was to bin-search at the depth K + v.depth and L was the vertex with the lowest in.time > v in.time and R was the vertex with the highest out.time < v out.time.