Help in a Problem from Brazilian TST

Revision en8, by Leonardo_Paes, 2019-11-23 02:58:33

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!

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English Leonardo_Paes 2019-11-23 03:09:26 0 (published)
en16 English 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 English Leonardo_Paes 2019-11-23 03:07:44 0 (published)
en14 English 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 English Leonardo_Paes 2019-11-23 03:02:18 0 (published)
en12 English Leonardo_Paes 2019-11-23 03:01:24 113
en11 English Leonardo_Paes 2019-11-23 03:00:07 192
en10 English Leonardo_Paes 2019-11-23 02:59:32 562
en9 English Leonardo_Paes 2019-11-23 02:59:13 140
en8 English Leonardo_Paes 2019-11-23 02:58:33 37
en7 English Leonardo_Paes 2019-11-23 02:56:49 109
en6 English Leonardo_Paes 2019-11-23 02:55:40 36 Tiny change: 'eq 10^5$).' -> 'eq 10^5$). Next $Q$ lines contain the queries.'
en5 English Leonardo_Paes 2019-11-23 02:54:06 64
en4 English 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 English Leonardo_Paes 2019-11-23 02:52:49 82
en2 English Leonardo_Paes 2019-11-23 02:48:56 175
en1 English Leonardo_Paes 2019-11-23 02:43:53 328 Initial revision (saved to drafts)