### practice080's blog

By practice080, 12 days ago,

Hi all, my friend asked me a question few months ago. But I still couldn't figure out the solution.

## Problem Statement

Given a tree with $N$ vertices ($v_1, ..., v_N$), among them, there is a source vertex $v_S$ and a destination vertex $v_E$ ($S \ne E$, $1 \le S,E \le N$). Each edge has an integer weight (can be negative, zero, or positive).

Alice starts at $v_S$ with an initial health value of $h$, and she wants to reach $v_E$. When she traverses through an edge with weight $w$, the weight $w$ is added to her health value. At any point in time, her health value cannot be negative. After an edge is used, the weight of the edge becomes $0$. Alice can use the same edge multiple times, but only the first time will affect her health value because the weight of the edge becomes $0$.

Find out whether Alice can reach $v_E$ with a non-negative health value.

## Constraint

$2 \le N \le 2 \times 10^5$ （for reference only, the expected solution's complexity needs to be better than $O(N^2)$)

## Example

To show why using the same edge multiple times is necessary, consider the following cases (using a degenerated tree for simplicity): $S = 3, E = 4, h = 1$

$v_1$ ---(2)--- $v_2$ ---(-1)--- $v_3$ ---(-2)--- $v_4$

The only path for Alice is $v_3 \to v_2 \to v_1 \to v_2 \to v_3 \to v_4$. Her health value will be $1 \to 0 \to 2 \to 2\to 2 \to 0$.

### Another example

• +16

 » 12 days ago, # |   +8 What about the constraints?
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 My friend mentioned the optimal solution is better than $O(N^2)$Updated: added the constaint
•  » » » 12 days ago, # ^ | ← Rev. 3 →   +9 Update: The solution is completely wrong because I forget the problem is on tree.I think I have come up with a solution.First you can find out all the connected block in the graph that only have positive edges, and then see all the points in a connected block as a whole point, it's obvious that once you enter a point, then you can increase your health by all the values in this connected block.So this inspire us to caculate the lowest value to reduce from the destination to get to the every connected block.Also, merge the connected blocks greedyly, if merge this two connected blocks brings positive health, then merge them, and check whether you can reach the destionations every time you merge a block.I think the merge part can be obtained by using a prority_queueSorry for my poor English, hope you can understand.
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   0 After the merge process, how do you find the answer?
•  » » » » » 12 days ago, # ^ |   0 merge process is start at the source point's connected block, so we just need to storage the minimum value from destinations to the block that we have merged, and check this value with the health we have now.
•  » » » » 12 days ago, # ^ |   0 During merging, do we only add positive edges into the connected block?
•  » » » » » 12 days ago, # ^ |   0 oh i think i have made some mistake, let me think more clearly.Sorry
•  » » » » » 12 days ago, # ^ |   0 Oh I forget it's a tree.Sorry for my blind-like behaves.
•  » » » » » » 12 days ago, # ^ |   0 It's ok, no worries haha
 » 12 days ago, # |   0 A similar problem 1734D - Slime Escape
•  » » 12 days ago, # ^ |   0 1734D is only a line instead of tree. Actually this problem is trivial if the tree degenerated to a star and $v_S$ is on the center of the star (line is a special case of star).
•  » » 10 days ago, # ^ |   0 could you briefly explain how to solve this qs? couldn't get the editorial for this qs properly. Thanks in advance!
 » 12 days ago, # |   0 I have a basic idea.let the health now you have be $H$.run a bfs first from the source point and rebuild the tree, in the new graph, every edge has the positive value but it has a limits which means an edge can be formed as $(u,v,w,l)$, you can gain $w$ health if $H \geq l$.After rebuilding the graph, expand the connected block from source point by greedy.If you can not expand any more, then you can just run the simulation from the closest point to the destinations and check.The complexity is $\mathcal{O}(n^2)$, you can storage all the points you could expand with a priority_queue, and check whether the limitation is reached and then expand.now the complexity is $\mathcal{O}(n \log n)$.
•  » » 12 days ago, # ^ |   0 How do you construct the new tree?
•  » » » 12 days ago, # ^ | ← Rev. 2 →   0 For example, this testcase:
•  » » » 12 days ago, # ^ |   0 Oh I made a mistake again, there might be some edges sharing the same the inner node.
 » 12 days ago, # |   +3 The important part of problem M from this contest https://codeforces.com/blog/entry/115769 solves your problem in O(NlogN). It's a shame that the editorials aren't being published directly in the cf posts but you can find both the statement and the editorial here: https://qoj.ac/contest/1221
•  » » 12 days ago, # ^ |   0 Thank you very much!
•  » » 12 days ago, # ^ |   0 maybe that greedy is not the important part of that problem anyway.and two problems have an vital difference because in this problem a node is not neccesary to be visit.
•  » » » 12 days ago, # ^ | ← Rev. 5 →   0 If you root at the starting point, then there's a path to the ending and branches to subtrees. Then it's a matter of using the max you can use from those subtrees, but you're right to say that the problems are different although you can use that problem's solution to solve this one by only merging things to the main path if they give positive contribution.An easier solution: dfs(u): bestBalance = 0 for each v child of u: bestBalance += max(0, dfs(v) + weight of the (u, v) edge) return bestBalance this dfs returns what you can squeeze out of a subtree. Call this on the hanging subtrees and use those that end up with positive value after considering the edge above it. In fact, this solution can be modified to solve (start, end) queries in O(logN) or maybe even better.
•  » » » » 12 days ago, # ^ |   0 In fact, this solution can be modified to solve (start, end) queries in O(logN) or maybe even better. What does the (start, end) queries refer to?
•  » » » » » 12 days ago, # ^ |   0 It means that queries would specify the source and destination, instead of them being fixed.
•  » » » » 12 days ago, # ^ | ← Rev. 3 →   0 Will the dfs code works for following case?h = 0E——(-100)——S——(-5)——v1——(200)——v2The right subtree of S contributes 195 to the bestBalance. But it is actually impossible to reach v2 because of the edge with weight of -5Did I miss anything?
•  » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 Sorry, I misread the statement when I said that. "At any point in time, her health value cannot be negative" I read that the opposite.I'm pretty sure that we can solve it with the first idea that I mentioned as I described. In the problem that I linked using an edge would first bring your HP down then you gain HP, which works with the condition of maintaining HP as non-negative.It'd look something like: root the tree at S. Start at S. When at a vertex, unlock the hanging subtrees (as in subtrees that don't belong to the S-E path). Unlocking means pushing their "compression" events into a heap to solve it like the editorial that I mentioned. When you get some event that wants to merge with the main path, then merge it if it ends up gaining you total HP and the "lose hp first" part doesn't send you to negative hp. Otherwise, break this process (keep the heap as is because you might be able to merge the event later) and try to move on to the next vertex in the S-E path. If you're able to reach E then the answer is yes.I think this works because actually we're only interested in events where vertices actually gain total HP. For those events, the exchange argument is that we merge the ones that lose the least hp first. I'm not completely sure how to prove this more or less formally since I've been introduced to this greedy algorithm only recently, so maybe someone can jump in here to help me.
•  » » » » » » 11 days ago, # ^ |   0 In the editorial: We take out the first monster to be defeated in the optimal order, and once its parent is defeated, we immediately have to defeat it too. Therefore, we merge it with its parent, reducing the problem size by 1, and iterate this process for n−1 rounds until the problem size is reduced to 1. I am not quite sure what does the optimal order obtained, and how do we merge the parent with children? For example, do we merge v1 and v2 in the example above?Besides, in the editorial, it mention that there will be $2^{(m−n+1)}$ trees, but is this number correct when a same vertex haves more than 2 incoming edges?For example, four vertex (1,2,3,4) and five edges(1-2, 2-3, 3-4, 1-4, 2-4). $2^{(m−n+1)} = 2^{(5-4+1)} = 4$, but we only have 3 trees: 1-2, 2-3, 1-4 1-2, 2-3, 2-4 1-2, 2-3, 3-4
•  » » » » » » » 11 days ago, # ^ |   0 The 2^(m-n+1) part isn't important to this blog but you're right to say it's not always that. The editorial's point for that is that 2^(m-n+1) is the worst case.The optimal order is obtained by applying the exchange argument in the same way as we would in an array. Then it's the same as problems like https://codeforces.com/problemset/gymProblem/102916/K and many others that have used this idea. I'm pretty sure Errichto's video about exchange argument has a problem exactly like that but in an array as well.
•  » » » » » » » » 11 days ago, # ^ | ← Rev. 3 →   0 Thanks for the explanation but I am still a bit unsure about the merging process, since the problem provided looks very different from this case. Is it possible to write a pseudocode? Besides, will that solution works on the following testcase?The possible path is v1-v3-v5-v7-v5-v3-v1-v2
•  » » » » » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 Yes. start at v1 unlock v4, v5, v6, v7, v8 as they are in a hanging subtree try to merge v8 to v6, you can do it and v6 is now "lose 100 hp and gain 200 hp after" try to merge v7 to v5, you can do it and v5 is now "lose 2 hp and gain 4 hp after" try to merge v5 to v3, you can do it and v3 is now "lose 2 hp and gain 4 hp" try to merge v3 to v1, you can do it since we have 2 hp and losing 2 hp to gain 4 is profit try to merge v6 to v4, v4 is now "lose 101 hp to gain 200" try to merge v4 to v3, but since v3 was merged with v1 we are actually trying to merge v4 to v1. We dont do it because losing 101 hp would bring us to negative hp. since we couldnt do it, try going to v2 and we can do it since we have profitted 2 hp. we reach v2 so it is possible luanmenglei also read this. In order to optimize the merges, we have vertices ordered by priority of merging in a heap. The priority is the same as the bloodseeker problem that I linked. When merging, we unite both vertices using DSU. A connected component's representant will be the one with lower height, so the one that's above every other one in the same component. After merging, we have to remove the current merge event from the parent in the heap and reinsert it with correct priority.In order to know the time when we could not expand edges not in the S-T path is: we simply keep the current HP, merge stuff that's outside of S-T path always except when it's being merged into the S-T path and merging it would lose enough HP to send us to negatives or it doesn't profit hp. After merging things into the S-T path, update the HP.About merges, if we say that a tuple (L, G) is (Loss of HP, Gain of HP), then merging (L1, G1) into (L2, G2) ends up with (min(L2, G2+L1+L2), G2+G1+L1+L2) since we're merging something that comes after into something. For the priority, simply refer to the bloodseeker problem or Errichto's video in this timestamp https://youtu.be/7hFWrKa6yRM?t=1500
•  » » » » » » » » » 11 days ago, # ^ | ← Rev. 3 →   0 I guess you mean (min(L2, L2+G2-L1), G2+G1)?Do you already have the merging priority in mind? It seems like your approach will always merge from leaf to root?
•  » » » » » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 I meant min(L2, L2+G2+L1), G2+G1+L1+L2), nicely spotted.I already linked a video talking about the priority, I won't say anything more about that.Now I see that that solution is wrong anyway. I don't see how to fix it anymore. The block idea that luanmenglei mentioned works by using exchange argument with small to large merging of subtree stuff. It's how I solved IOI19JOBS (warmup problem) when someone asked me about that problem and I'm sure that it works for this problem but it's tricky and I don't feel like explaining it in detail right now right now. The idea is simply to summarize a subtree by having blocks of vertices that you will take all at once and merging blocks if the root block is worse than the next block. You can also create this block structure with the idea from the editorial that I mentioned, but as I said I don't know that idea that well.
•  » » » » » » » » » 11 days ago, # ^ | ← Rev. 3 →   0 Hi tfg, really thank you for sharing all of the resources and sharing! I already watched the youtube video :DDo you mind to point out why that solution is wrong (maybe share a testcase)?
•  » » » » » » » » » 11 days ago, # ^ | ← Rev. 4 →   0 Wait, it might not be wrong. I got confused because there are 2 ways of summarizing stuff: (L, G) as I explained and (loss of HP you need to pay to enter here, total profit) as in (L, G+L) if L is negative.Also, after the merge we have actually (min(L2, L2 + G2 + L1), G2+G1+L1+L2 — min(L2, L2 + G2 + L1))) because I forgot that I usually use L being <= 0.I'm back to thinking this solution works :| it's just that the merge itself is a bit confusing if you don't think about it carefully.
•  » » » » » » » » » 11 days ago, # ^ | ← Rev. 11 →   0 For the (min(L2, L2 + G2 + L1), G2+G1+L1+L2 — min(L2, L2 + G2 + L1))) The first part is loss of HP to enter the vertex The second part is profit + loss of HP after enter the vertexSo, the final HP after entering the vertex = original HP + first part + second part.Is that correct?I have an idea to construct the counter example for this merging approach but I am not too sure. Without knowing the ordering priority, its hard for me to test it. The high level idea is to find a scenario such that all leafs having higher priority than others and they will merge to an internal node, but that causes the first part (loss of HP) of that internal node becomes too big (too negative). Instead we might don’t want to merge some leafs into that internal node. Not sure whether this works..Something like:
•  » » » » » » » » » 10 days ago, # ^ |   0 When things profit total HP, the priority is by order of loss of HP. Losing less HP means higher priority. So after merging (-1, 0) and (-2, 5), we'll have (-3, 5) (I'm sure it's this, maybe the formula that I sent ealier might be wrong) and that has higher priority than (-6, 10) and (-20, 100).
•  » » » » » » » » » 10 days ago, # ^ | ← Rev. 2 →   0 But (-1,0) does not profit, it is unsure that whether its subtree will profit before u finish the processing of its whole subtree. In this case, the subtree makes it profit in the end
•  » » » » » » » » » 10 days ago, # ^ |   0 But (-2, 5) that does profit is merged into the (-1, 0), making it profit. (-2, 5) has higher priority than (-1, 0).
•  » » » » » » » » » 7 days ago, # ^ |   +10 I'm pretty sure the merging idea works, too -- the way I think about it is that you're creating an equivalent tree satisfying the following properties: The reward of every node is positive (it only makes sense to visit a node if you'll gain from it) For any node, requiredHP[v] >= requiredHP[parent[v]] (so you don't visit nodes out of order) Now when processing node v, if the reward is already positive, there is nothing to do. If the reward is negative, we want to check what is the lowest possible value of requiredHP[v] that we need to make the reward positive by exploring some of the subtree (if the reward can't be made positive, delete this subtree, it's useless). I'm not going to prove this formally either but you can argue that the best strategy is visiting the nodes in the subtree in order of requiredHP, and you can merge those to v to maintain the first invariant. To maintain the second invariant, merge all descendants with requiredHP[d] <= requiredHP[v] to v.Having the equivalent tree, the original problem is easy as you just take side-paths as long as you can (since all rewards are positive).
•  » » » » » » » » » 7 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } lowest possible value of requiredHP[v] that we need to make the reward positive by exploring some of the subtree Isn’t this just the absolute value of the negative value?
•  » » » » » » 11 days ago, # ^ | ← Rev. 3 →   0 not every vertices are required to visit, so this greedy have some issues.just as the testcase below: Imgur the source point is 1, destination is 4
•  » » » » » » » 11 days ago, # ^ |   +5 The greedy that I described works for that case. I suggest you to read it word by word again and again.
•  » » » » » » » » 11 days ago, # ^ |   0 Oh sorry for i haven't read your latest comment.Your idea is same as my idea which I told to practice080 in the talk section (we're using the native language), but the process seems to be $\mathcal{O}(n^2)$, how do you optimise it or i misread something?
•  » » » » » » » » 11 days ago, # ^ |   0 More clearly, how to know the time when we could not expand edges not in the S-T path anymore
 » 12 days ago, # |   0 Should we output the answer for each vertex to each vertex? or the input consists only of N,S,E?
•  » » 12 days ago, # ^ |   0 Only for S to E, the output will be a single boolean
 » 10 days ago, # |   0 Maybe you should collect as much health as possible, return to the source node, and then go to the end node and see if you end up with a positive number?
 » 6 days ago, # |   0 No