Road Projects
Contest: Educational Codeforces Round 48 (Rated for Div. 2)
Difficulty rating: 2600
Tags: dfs and similar, dp, trees

There are $$$n$$$ cities in the country of Berland. Some of them are connected by bidirectional roads in such a way that there exists exactly one path, which visits each road no more than once, between every pair of cities. Each road has its own length. Cities are numbered from $$$1$$$ to $$$n$$$.

The travelling time between some cities $$$v$$$ and $$$u$$$ is the total length of the roads on the shortest path from $$$v$$$ to $$$u$$$.

The two most important cities in Berland are cities $$$1$$$ and $$$n$$$.

The Berland Ministry of Transport decided to build a single new road to decrease the traffic between the most important cities. However, lots of people are used to the current travelling time between the most important cities, so the new road shouldn't change it too much.

The new road can only be built between such cities $$$v$$$ and $$$u$$$ that $$$v \neq u$$$ and $$$v$$$ and $$$u$$$ aren't already connected by some road.

They came up with $$$m$$$ possible projects. Each project is just the length $$$x$$$ of the new road.

Polycarp works as a head analyst at the Berland Ministry of Transport and it's his job to deal with all those $$$m$$$ projects. For the $$$i$$$-th project he is required to choose some cities $$$v$$$ and $$$u$$$ to build the new road of length $$$x_i$$$ between such that the travelling time between the most important cities is maximal possible.

Unfortunately, Polycarp is not a programmer and no analyst in the world is capable to process all projects using only pen and paper.

Thus, he asks you to help him to calculate the maximal possible travelling time between the most important cities for each project. Note that the choice of $$$v$$$ and $$$u$$$ can differ for different projects.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$) — the number of cities and the number of projects, respectively.

Each of the next $$$n - 1$$$ lines contains three integers $$$v_i$$$, $$$u_i$$$ and $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$) — the description of the $$$i$$$-th road. It is guaranteed that there exists exactly one path, which visits each road no more than once, between every pair of cities.

Each of the next $$$m$$$ lines contains a single integer $$$x_j$$$ ($$$1 \le x_j \le 10^9$$$) — the length of the road for the $$$j$$$-th project.

Output format:
Print $$$m$$$ lines, the $$$j$$$-th line should contain a single integer — the maximal possible travelling time between the most important cities for the $$$j$$$-th project.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The road network from the first example:

You can build the road with length $$$1$$$ between cities $$$5$$$ and $$$6$$$ to get $$$83$$$ as the travelling time between $$$1$$$ and $$$7$$$ ($$$1 \rightarrow 2 \rightarrow 6 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$ $$$=$$$ $$$18 + 4 + 1 + 12 + 24 + 24 = 83$$$). Other possible pairs of cities will give answers less or equal to $$$83$$$.

Example input:
7 2
1 2 18
2 3 22
3 4 24
4 7 24
2 6 4
3 5 12
1
100

Example output:
83
88

Editorial:
The first solution (editorial by PikMike)
Firtsly, we can notice that we get the most profit by placing the edge in a same position, no matter the query. Moreover, once you have calculated the minimum difference you can apply to the shortest path $$$dif_{min}$$$ by adding edge of the weight $$$0$$$, you can answer the queries in $$$O(1)$$$ each. Let the current shortest distance between $$$1$$$ and $$$n$$$ be $$$curd$$$. Then the answer to some query $$$x$$$ is $$$min(curd, curd - mind + x)$$$.
Let's proceed to proofs of the following. Consider any of the optimal positions for the edge of weight $$$0$$$. Then weight $$$1$$$ will add $$$1$$$ to the answer in this position (if the path isn't $$$curd$$$ already but that is trivial). Let there be another position such that the answer in it is less than the current one. That means that the answer for weight $$$0$$$ in it is less by $$$1$$$ which is smaller than the first one we got, which leads to contradiction. The second fact can deduced from the first one.
Then let me introduce the next bold statement. We root the tree with vertex $$$1$$$. Then if there exists such a vertex in that it's not an ancestor of vertex $$$n$$$ and the number of vertices in its subtree (inclusive) is greater than $$$1$$$ then $$$dif_{min} = 0$$$. That is simple: just put the edge between the parent of this vertex and any of vertices of the subtree, there always be such that the edge doesn't exist yet. That won't change the shortest path, no matter which $$$x$$$ it is.
Then, we have a graph of the following kind:

That is the simple path between $$$1$$$ and $$$n$$$ and some vetices on it have additional children leaves. Finally, let's proceed to the solution.
We want to choose such a pair of vertices that the sum of edge on a path between them, which are also a part of the path between $$$1$$$ and $$$n$$$ plus the weights of the newly included to shortest path edges (if any) is minimal possible. Let's precalc $$$d_v$$$ — the sum of weights of edges from vertex $$$1$$$ to vertex $$$v$$$ and $$$p_v$$$ — parent of vertex $$$v$$$. Let $$$w(v, u)$$$ be the weight of an edge between $$$v$$$ and $$$u$$$. Then we end up with the four basic cases for these vertices $$$v$$$ and $$$u$$$ with $$$v$$$ having greater or equal number of edges on path to $$$1$$$ than $$$u$$$: each of the form (whether $$$v$$$ belongs to the simple path between $$$1$$$ and $$$n$$$, whether $$$u$$$ belongs to it).
• $$$u$$$ doesn't belong: the answer is $$$d_v + w(p_u, u) - d[p_u]$$$;
• $$$u$$$ belongs, $$$v$$$ doesn't: $$$d_u + w(p_v, v) - d[p_v]$$$;
• both belongs: $$$d_v - d_u$$$.
Each of these formulas can be broken down to parts with exacly one of the vertices. Let's call them $$$pt_v$$$ and $$$pt_u$$$. That means minimizing the result is be the same as minimizing each of the parts.
We run depth-first search on vertices which belong to a simple path between $$$1$$$ and $$$n$$$ inclusive. Maintain the minimum value of $$$pt_u$$$ you have already passed by. Try connecting each vertex with this $$$u$$$ and also parent of the parent of the current vertex using all the possible formulas and updating $$$dif_{min}$$$ with the resulting value.
Finally, after the precalc is finished, asnwer the queries in $$$O(1)$$$ with $$$dif_{min}$$$.
Overall complexity: $$$O(n + q)$$$.
The second solution (editorial by BledDest)
Let's denote the distance from vertex $$$1$$$ to vertex $$$x$$$ in the tree as $$$d_1(x)$$$. Similarly, denote the distance from $$$n$$$ to $$$x$$$ in the tree as $$$d_n(x)$$$.
Suppose we try to add a new edge between vertices $$$x$$$ and $$$y$$$ with length $$$w$$$. Then two new paths from $$$1$$$ to $$$n$$$ are formed: one with length $$$d_1(x) + w + d_n(y)$$$, and another with length $$$d_1(y) + w + d_n(x)$$$. Then the new length of shortest path becomes $$$min(d_1(n), d_1(x) + w + d_n(y), d_1(y) + w + d_n(x))$$$. So if we find two non-adjacent vertices such that $$$min(d_1(x) + d_n(y), d_1(y) + d_n(x))$$$ is maximum possible, then it will always be optimal to add an edge between these two vertices.
How can we find this pair of vertices? Firstly, let's suppose that $$$d_1(x) + d_n(y) \le d_1(y) + d_n(x)$$$ — when we pick vertex $$$x$$$, we will try to pair it only with vertices $$$y$$$ corresponding to the aforementioned constraint. This can be done by sorting vertices by the value of $$$d_1(x) - d_n(x)$$$ and then for each vertex $$$x$$$ pairing it only with vertices that are later than $$$x$$$ in the sorted order.
How do we find the best pair for $$$x$$$? The best pair could be just the vertex with maximum possible $$$d_n(y)$$$, but it is not allowed to connect a vertex with itself or its neighbour. To handle it, we may maintain a set of possible vertices $$$y$$$, delete all neighbours of $$$x$$$ from it, pick a vertex with maximum $$$d_n$$$, and then insert all neighbours of $$$x$$$ back into the set.
This solution works in $$$O(n \log n + q)$$$ time.