Help in a Problem from Brazilian TST

Revision en12, by Leonardo_Paes, 2019-11-23 03:01:24

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$ 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$ — 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

#### History

Revisions

Rev. Lang. By When Δ Comment
en17 Leonardo_Paes 2019-11-23 03:09:26 0 (published)
en16 Leonardo_Paes 2019-11-23 03:09:17 21 Tiny change: '$and$V$and it as' -> '$ and $V$ representing an edge and it as' (saved to drafts)
en15 Leonardo_Paes 2019-11-23 03:07:44 0 (published)
en14 Leonardo_Paes 2019-11-23 03:07:26 17 Tiny change: 'and $V_i$ — the i-t' -> 'and $V_i$ ($U_i$ != $V_i$) — the i-t' (saved to drafts)
en13 Leonardo_Paes 2019-11-23 03:02:18 0 (published)
en12 Leonardo_Paes 2019-11-23 03:01:24 113
en11 Leonardo_Paes 2019-11-23 03:00:07 192
en10 Leonardo_Paes 2019-11-23 02:59:32 562
en9 Leonardo_Paes 2019-11-23 02:59:13 140
en8 Leonardo_Paes 2019-11-23 02:58:33 37
en7 Leonardo_Paes 2019-11-23 02:56:49 109
en6 Leonardo_Paes 2019-11-23 02:55:40 36 Tiny change: 'eq 10^5$).' -> 'eq 10^5$). Next $Q$ lines contain the queries.'
en5 Leonardo_Paes 2019-11-23 02:54:06 64
en4 Leonardo_Paes 2019-11-23 02:53:18 53 Tiny change: ' \leq 10^5).' -> ' \leq 10^5$). The next$N-1\$ lines contain the edges of the tree.'
en3 Leonardo_Paes 2019-11-23 02:52:49 82
en2 Leonardo_Paes 2019-11-23 02:48:56 175
en1 Leonardo_Paes 2019-11-23 02:43:53 328 Initial revision (saved to drafts)