Leonardo_Paes's blog

By Leonardo_Paes, history, 2 weeks 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

»
2 weeks 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).

»
2 weeks 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?