Happy New Year: Problem F video tutorial (little tad abstract)
379F - New Year Tree
Video Link
I wanted to go into details — but it would have been a full 30 minutes. Any suggestion/query is welcome.
I don't think your solution can pass the system test. I think it will be TLE. In the worst case, updating the nodes' information can be O(n); So it's O(q*n)? Did I misunderstand? :D
updating will take O(log(n)) per query. Something like:
cin >> current_query_node; new_node_first = current_query_node + 1; new_node_second = new_node_first+1; P[new_node_first][0] = P[new_node_second][0] = current_query_node; for (j = 1; 1 << j < N; j++) P[new_node_first][j] = P[new_node_second][j] = P[P[new_node_first][j - 1]][j - 1];
So, we are building the data structure for LCA incrementally after each query.
For more info check out "Another easy solution in <O(N logN, O(logN)>" section on TC
I don't think your solution can pass the system test. I think it will be TLE. In the worst case, updating the nodes' information can be O(n); So it's O(q*n)? Did I misunderstand? :D
updating will take O(log(n)) per query. Something like:
So, we are building the data structure for LCA incrementally after each query.
For more info check out "Another easy solution in <O(N logN, O(logN)>" section on TC