Tree queries

Questions 1 to 5 of 8

1. 1. An AI tool says that binary lifting answers each LCA query in O(1) time once the table is built, the same as an Euler tour with a sparse table. Is this right?

   Yes. The table holds every ancestor, so a query is one lookup.Yes, but only when the tree is a path, because a path has one ancestor per depth.No. Binary lifting walks the parents one step at a time, so each query costs O(n).No. Binary lifting makes one jump per bit of the depth, so a query costs O(log n). The O(1) query belongs to the Euler tour with a sparse table.
2. 2. A binary lifting table is built for a tree with n = 200000 vertices, using the loop while ((1 << LOG) <= n) LOG++. How many levels does LOG end up as?

   Type a number.

3. 3. Take the 7-vertex tree from the tree DP lesson: edges 0-1, 0-2, 1-3, 1-4, 2-5 and 5-6, rooted at 0. The sum of distances from vertex 0 to all other vertices is 11. Using the rerooting rule ans[v] = ans[p] - sz[v] + (n - sz[v]), what is the sum of distances from vertex 1? Here sz[1] = 3.

   Type a number.

4. 4. An AI wrote heavy-light decomposition code for path sums. Its loop decides which vertex to move up by comparing depth[u] and depth[v], the depths of the two current vertices, not the depths of their chain heads. It passes the sample, where both ends are on one chain. What is the most likely failure?

   The sum is always one value too large, because the LCA is counted twice.The program is too slow, because the loop walks one vertex at a time and never uses the chains.The sum is wrong on paths that cross a chain boundary, because the loop can skip part of the path before the two vertices reach the same chain.The segment tree gets the wrong start position, so every range sum is shifted by one.
5. 5. Which statements about heavy-light decomposition are true? Assume the decomposition uses a DFS that visits the heavy child first.

   Pick every answer that is true.

   Going from any vertex up to the root crosses at most log2 n light edges.Each heavy chain takes a block of consecutive positions in the array.A subtree takes a block of consecutive positions in a BFS order, so BFS works for subtree queries.A path query takes O(log^2 n) time, because there are about 2 log n chain pieces and each piece is a segment tree range query costing O(log n).