P8602 [Lanqiao Cup 2013 NOI Qualifier A] The Minister’s Travel Expenses

A long time ago, the Kingdom of $T$ was extremely prosperous. To better manage the country, the kingdom built many expressways to connect the capital with major cities. To save money, the ministers of $T$ designed an excellent construction plan so that every major city can be reached from the capital either directly or indirectly through other major cities. Also, if you do not pass through any major city more than once, then the route from the capital to each major city is unique. $J$ is an important minister of $T$. He travels among the cities to observe people’s lives. Therefore, traveling nonstop from one city to another is what $J$ does most often. He has a money bag to store the travel expenses between cities. The smart minister $J$ found that if he does not stop to rest in any city, then during continuous traveling, the expense he pays depends on the distance he has already traveled. For the $1$ kilometer from the $(x - 1)$-th kilometer to the $x$-th kilometer (where $x$ is an integer), the expense is $x + 10$. That is, traveling $1$ kilometer costs $11$, and traveling $2$ kilometers costs $23$. Minister $J$ wants to know: starting from some city and arriving at another city without resting in between, among all possible travel expenses, what is the maximum?

The first line contains an integer $n$ ($n \le 10^5$), the number of cities in the Kingdom of $T$, including the capital. Cities are numbered from $1$ to $n$, where city $1$ is the capital. The next $n - 1$ lines describe the expressways of $T$ (there are exactly $n - 1$ expressways). Each line contains three integers $P_i, Q_i, D_i$, indicating that there is an expressway between city $P_i$ and city $Q_i$ with length $D_i$ ($D_i \le 1000$) kilometers.

Output one integer, the maximum travel expense that Minister $J$ may spend.

Sample explanation: Minister $J$ traveling from city $4$ to city $5$ costs $135$. Time limit: 5 seconds, 64 MB. Lanqiao Cup 2013, the 4th provincial contest. Translated by ChatGPT 5