mkagenius's blog

Happy New Year: Problem F video tutorial (little tad abstract)
By mkagenius, 12 years ago, In English

379F - Новогоднее дерево

Video Link

I wanted to go into details — but it would have been a full 30 minutes. Any suggestion/query is welcome.

  • Vote: I like it
  • -1
  • Vote: I do not like it

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

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

→ Reply
  • »
    »
    12 years ago, hide # ^ |
    ← Rev. 7  
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply