Leonardo_Paes's blog

By Leonardo_Paes, history, 4 years ago, In English

Hi. This problem is from the Brazilian team selection test for the IOI and I don't know anyone that solved it nor the official solution. Any help would be appreciated!

Link to the original statement in portuguese and judge to submit: https://neps.academy/problem/353

Simplified Statement: You are given an unweighted undirected tree with $$$N$$$ nodes and $$$Q$$$ queries. Each query gives two nodes $$$U$$$ and $$$V$$$ representing an edge and it asks for the maximum path that goes through it. Note that this edge might not be in the initial tree and if this is the case it will only exist in this query.

Input: The first line contains only the integer $$$N$$$ ($$$2 \leq N \leq 10^5$$$). The next $$$N-1$$$ lines contain the edges of the tree. Next line contains only the integer $$$Q$$$ ($$$1 \leq N \leq 10^5$$$). Next $$$Q$$$ lines contain two nodes $$$U_i$$$ and $$$V_i$$$ ($$$U_i \neq V_i$$$) — the i-th query.

Output: Print $$$Q$$$ integers — the answers to the queries in the order the queries appear in the input.

Example Input:

5
1 2
2 3
2 4
1 5
2
4 5
1 2

Example Output:

4
3

  • Vote: I like it
  • +11
  • Vote: I do not like it

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

Auto comment: topic has been updated by Leonardo_Paes (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What do you mean by "maximum path that goes through it"? Maximum length among paths through this edge? And should we only consider simple paths?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This problem is at least partially my fault (I came up with the first official solution, which was later very simplified by the other testers), so I guess I should try to explain it. I'll assume you're very familiar with binary lifting, as it's going to get used a lot; otherwise you should probably be solving easier problems first.

What the problem is asking for boils down to: given two nodes U and V in a tree, find two disjoint paths (one starting at U and one starting at V) such that the sum of the lengths of the paths is maximized.

For two nodes U and V, let their LCA be L. We have a few cases here:

1) One of the paths goes to the ancestor of L (suppose it's from U). Then it must go to the vertex not in the subtree of L that is farthest from L; we can precompute those for all possible L with a DFS to answer this in constant time.

The other path is more interesting: it starts at V, goes to some ancestor between V and L, then goes down to a leaf. Let A[v][p] be the max path that can be formed this way between v and the $$$2^p$$$ ancestor of v; I'll leave out the exact details but you can compute A[v][p] from A[v][p-1] using binary lifting, and having this information allows you to answer the query in logarithmic time.

2) None of the paths goes to the ancestor of L. Let's flatten the path between U and V in the tree and imagine it as a line with some branches coming out:

Now the solution is that the red path goes up to vertex i in the line, the blue path goes up to vertex j in the line, and then they go as far down the branch as they can. Assuming the distance between u and v is D, this gives a final length sum of (i) + (D — j) + branchLength[i] + branchLength[j] = D + (branchLength[i] + i) + (branchLength[j] — j).

You can compute the optimal value of this function using a segtree: for a given segment, if you split it in the middle, either optimal i and j are both on the same side or they cross the middle; in this last case you can take the best (branchLength[x] + x) from the left and the best (branchLength[x] — x) from the right.

Going back to the original problem it happens that we are not dealing only with a line, but a tree. There are at least two ways you can solve this problem:

  • We can augment our previous binary lifting to save the day again. If you understood the segtree above for the line case this is a lot easier since in fact, this solution is almost completely analogous: the information stored in A[v][p] is the same as the information stored in the nodes of the segtree, and the function to merge two nodes in the segtree is exactly how you compute A[v][p] from A[v][p-1] here as well.
  • (How I originally did it) Notice that if case 2 is optimal, then the path between U and V crosses the diameter of the tree. Therefore you can make the previously described segment tree treating the diameter as the line and when processing the query you lift U and V until they hit the diameter to query this segment tree. This can get pretty messy to code, but if you can get all of the many implementation details right it is a correct solution.