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

I have been thinking about a problem for a while. It is from OBI, the Brazilian Olympiad in Informatics. Can anyone give me some ideas/solutions to the problem? Sorry if there are some mistakes in the translation.
Original link: https://olimpiada.ic.unicamp.br/pratique/p2/2011/f1/quadrado/
This is the statement:

Given an $$$N$$$ x $$$N$$$ matrix, a good choice of cells is a choice that every row and every column of the matrix has exactly one cell chosen. An arithmetic square of size $$$N$$$ and sum $$$S$$$ is a matrix of integers of $$$N$$$ lines and $$$N$$$ columns that all good choices has sum $$$S$$$ and all the numbers in the matrix are distinct. Your task in this problem is to generate an arithmetic square of size $$$N$$$ and sum $$$S$$$, given $$$N$$$ and $$$S$$$. Each absolute value of the matrix has to be lower or equal to $$$10^9$$$.

Input: $$$N$$$ and $$$S$$$, both integers with absolute value between $$$1$$$ and $$$1000$$$, inclusive. $$$S$$$ can be negative and $$$N$$$ is positive.

Output: Any possible matrix that is an arithmetic square of size $$$N$$$ and sum $$$S$$$.

Input 1:
2 49

Output 1:
23 40
9 26

Input 2:
3 53

Output 2:
-41 -29 2
28 40 71
11 23 54

Input 3:
1 -55

Output 3:
-55