Help in a Problem from Brazilian TST

Правка en9, от Leonardo_Paes, 2019-11-23 02:59:13

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.

Example Input: 5
1 2 2 3 2 4 1 5 2 4 5 1 2

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)