Auto comment: topic has been updated by Friren (previous revision, new revision, compare).

This is a very powerful technique known as "Euler Tour Tree" — (wiki, codeforces tutorial)

It's often a possible alternative to HLD when dealing with path queries, and it's also much more powerful when the tree may change structure.

The basic idea is that we do a full DFS of the tree and keep it as one long path, by considering edges both ways, i.e. we add the node to the path both when going down a child of his and upon returning back to it (essentially thinking of each undirected edge as two directed edges).

Now back to the concrete problem. Here the solution uses this technique but also keeps weights of the edges — an undirected edge of weight W is split into one edge going from parent to child with weight +W and one edge going from child to father with weight -W (the tree is arbitrarily rooted at 1). These are then kept as a big list in the Euler-tour order.

Now let's try to reason about how paths look in this flattened structure. Suppose we take two nodes $$$A$$$ and $$$B$$$ and find them on positions $$$p_a$$$ and $$$p_b$$$ respectively and let $$$p_a<p_b$$$ w.l.o.g. Let $$$C$$$=$$$LCA(A,B)$$$ on position $$$p_c$$$ with some $$$p_a\leq p_c\leq p_b$$$ (this is guaranteed to exist because of the way we build the Euler tour). What we have to notice is that from the point of view of $$$A$$$, following the tour, we will eventually climb up to $$$C$$$, and then eventually climb down to $$$B$$$. Any detours outside of this $$$A-C-B$$$ path will sum up to 0 in terms of weights, because each edge going down will be negated by the edge coming back up. So if we consider the sequence of weights, we can calculate the distance between $$$A$$$ and $$$B$$$ by adding up all weights from $$$A$$$ to $$$C$$$ (i.e. between $$$p_a$$$ and $$$p_c$$$) with negative sign, and then adding all weights from $$$C$$$ to $$$B$$$ (i.e. between $$$p_c$$$ and $$$p_b$$$) with positive sign. So if we consider only the subarray from $$$p_a$$$ to $$$p_b$$$, the distance between the two nodes is to negate some prefix and then sum up the subarray. Furthermore, the "correct" prefix to negate is exactly the one that maximizes the sum of the whole subarray, because we negate exactly all the upwards climbing.

Extrapolating from this idea, it is the case that the subarray which maximizes "negation of a prefix + the rest" is going to be the diameter, as that just describes the largest distance between some two vertices. I'm purposefully handwavy and not proving things rigorously, as I'm going more for intuition here.

Well, now the problem is fully translated to:

Given a sequence of N integers, find the maximal subarray if you're allowed to negate a prefix of values once.

Well, this is now solvable with segment trees, and that is all that the solution you linked is doing. Let me know if you can't figure out why the code presented is solving that problem, but otherwise I'll let you think about it yourself now that you know the problem transformation.