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
Auto comment: topic has been updated by Leonardo_Paes (previous revision, new revision, compare).
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?
Yes and Yes!
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:
Thank you so much!