In last educational problem C, I submitted what I thought was a wrong code (I even resubmmited shortly after). I didn't declare my answer variable as a long long, even though the worst case is 5000^3 which exceeds 10^10. Here is my code https://codeforces.me/contest/2182/submission/355744056

I suspect something weird is happening in the last cout, where the compiler is treating it as a long long, even though there is an int and an unsigned int being multiplied.

Any help is appreciated!

1999/2000 ms

1. 02:57:15 Unsuccessful hacking attempt
2. 03:13:10 Unsuccessful hacking attempt
3. 03:13:18 Unsuccessful hacking attempt
4. 03:13:53 Unsuccessful hacking attempt
5. 03:13:59 Unsuccessful hacking attempt
6. 03:14:16 Unsuccessful hacking attempt
7. 03:17:38 Unsuccessful hacking attempt
8. 03:19:16 Unsuccessful hacking attempt
9. 03:19:30 Unsuccessful hacking attempt
10. 03:20:19 Unsuccessful hacking attempt
11. 03:20:21 Unsuccessful hacking attempt
12. 03:20:49 Unsuccessful hacking attempt
13. 03:21:31 Unsuccessful hacking attempt
14. 03:21:54 Unsuccessful hacking attempt
15. 03:22:12 Unsuccessful hacking attempt
16. 03:22:33 Unsuccessful hacking attempt
17. 03:23:01 Unsuccessful hacking attempt
18. 03:23:19 Unsuccessful hacking attempt
19. 03:23:56 Unsuccessful hacking attempt
20. 03:24:45 Unsuccessful hacking attempt
21. 03:32:37 Unsuccessful hacking attempt
22. 03:43:11 Unsuccessful hacking attempt
23. 03:44:49 Unsuccessful hacking attempt
24. 03:45:17 Unsuccessful hacking attempt
25. 03:49:26 Unsuccessful hacking attempt
26. 03:52:07 Unsuccessful hacking attempt
27. 03:54:15 Unsuccessful hacking attempt
28. 03:54:44 Unsuccessful hacking attempt
29. 04:07:35 Unsuccessful hacking attempt
30. 04:09:54 Unsuccessful hacking attempt
31. 04:10:08 Unsuccessful hacking attempt
32. 04:20:09 Unsuccessful hacking attempt
33. 04:37:57 Unsuccessful hacking attempt
34. 04:39:22 Unsuccessful hacking attempt
35. 04:45:43 Unsuccessful hacking attempt
36. 04:49:15 Unsuccessful hacking attempt
37. 04:52:11 Unsuccessful hacking attempt
38. 05:09:40 Unsuccessful hacking attempt
39. 05:56:25 Unsuccessful hacking attempt
40. 05:57:03 Unsuccessful hacking attempt
41. 06:55:06 Unsuccessful hacking attempt
42. 08:05:42 Unsuccessful hacking attempt
43. 09:35:15 Unsuccessful hacking attempt
44. 10:12:43 Unsuccessful hacking attempt
45. 10:18:41 Unsuccessful hacking attempt
46. 10:22:24 Unsuccessful hacking attempt
47. 10:23:44 Unsuccessful hacking attempt
48. 10:31:17 Unsuccessful hacking attempt
49. 10:36:35 Unsuccessful hacking attempt
50. 11:35:52 Unsuccessful hacking attempt
51. 11:37:09 Unsuccessful hacking attempt
52. 11:37:34 Unsuccessful hacking attempt
53. 11:46:50 Unsuccessful hacking attempt
54. 11:46:56 Unsuccessful hacking attempt
55. 11:50:31 Unsuccessful hacking attempt
56. 11:52:25 Unsuccessful hacking attempt
57. 12:03:54 Unsuccessful hacking attempt
58. 12:04:32 Unsuccessful hacking attempt
59. 12:10:46 Unsuccessful hacking attempt
60. 12:12:56 Unsuccessful hacking attempt
61. 12:13:54 Unsuccessful hacking attempt
62. 12:36:01 Unsuccessful hacking attempt
63. 12:37:40 Unsuccessful hacking attempt
64. 12:43:01 Unsuccessful hacking attempt
65. 12:45:35 Unsuccessful hacking attempt
66. 12:49:09 Unsuccessful hacking attempt
67. 12:50:55 Unsuccessful hacking attempt
68. 13:06:04 Unsuccessful hacking attempt
69. 13:09:44 Unsuccessful hacking attempt
70. 13:11:34 Unsuccessful hacking attempt
71. 13:12:07 Unsuccessful hacking attempt
72. 13:12:48 Unsuccessful hacking attempt
73. 13:13:34 Unsuccessful hacking attempt
74. 13:27:01 Unsuccessful hacking attempt
75. 13:28:41 Unsuccessful hacking attempt
76. 13:31:04 Unsuccessful hacking attempt
77. 13:32:33 Unsuccessful hacking attempt
78. 13:34:26 Unsuccessful hacking attempt
79. 13:34:57 Unsuccessful hacking attempt
80. 13:35:46 Unsuccessful hacking attempt
81. 13:36:05 Unsuccessful hacking attempt
82. 13:36:19 Unsuccessful hacking attempt
83. 13:36:27 Unsuccessful hacking attempt

Blessed by the $$$O(n^2 \log n)$$$ no-brainer! Try harder hacking next time :P

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