In this problem for 100 pts needed to use centroid or hld, but I found the one submussion that solved it just with segment tree, which make curious, but merge function I still cannot understand it. Can someone explain it to me, I am trying to upsolve it for 3 days straight.
seg[ind].pref=max(seg[2*ind+1].pref, seg[2*ind+1].sum+seg[2*ind+2].pref);
seg[ind].suff=max(seg[2*ind+2].suff, -seg[2*ind+2].sum+seg[2*ind+1].suff);
seg[ind].sum=seg[2*ind+1].sum+seg[2*ind+2].sum;
seg[ind].allans=max(seg[2*ind+1].allans+seg[2*ind+2].sum, -seg[2*ind+1].sum+seg[2*ind+2].allans);
seg[ind].prefans=max({seg[2*ind+1].prefans, seg[2*ind+1].allans+seg[2*ind+2].pref, -seg[2*ind+1].sum+seg[2*ind+2].prefans});
seg[ind].suffans=max({seg[2*ind+2].suffans, seg[2*ind+2].allans+seg[2*ind+1].suff, seg[2*ind+2].sum+seg[2*ind+1].suffans});
seg[ind].ans=max({seg[2*ind+1].ans, seg[2*ind+2].ans, seg[2*ind+1].suffans+seg[2*ind+2].pref, seg[2*ind+1].suff+seg[2*ind+2].prefans});
I didnt get allans,prefans,suffans, their value, what their values represent? Hope for your help!
P.S downvotes are welcome, I know this is again stupid blog of beggin help from newbies.
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.
Thanks a lot!!! Eventually a step in this problem, but now i cannot understood idea of finding a max continuous subarray with negating prefix once( Several hours and maybe I find out the answer!)
Give it some time to try and grasp the ideas here, if you haven't heard of Euler Tour Trees then it's normal for this whole thing to take you a while to internalize.
If you are stuck after some serious thoughts, formulate exactly what confuses you and I can elaborate.
Last thing that confuse me — why we are negating sum of second part in max function of suffix. seg[ind].suff=max(seg[2*ind+2].suff, (this one)-seg[2*ind+2].sum+seg[2*ind+1].suff);
i thought suff must show max suff without negating, but there something else.(in prefix is that as I thought). so in suffix we must keep in mind, that it may start with negating, but in suffans: g[x*2+1].allans + g[x*2].suff. Allans also may start with negating, but suff start always without negating, so by adding them, we are negating subarray in middle of them, but we must only negate prefix? It may sound confusing, I will draw illustration
here what i mean. red — negated part. black — not negated part. So in result we are negating not prefix, a subarray in the middle, that go against idea
Thanks after all !!! Now i can confidently say that Im fully upsolved this question only with your help. Thank you !!!
Did you manage to understand the last question you asked yourself?
Yep! suff and suffans are always negated, that things was the last part of a puzzle.
Great job! Glad to help someone who actually puts in the effort.