[GP of Kazan]Fast Spanning Tree

Difficulty Ratings

Idea Creativity: 4/5
Techniques Used: 3/5
Implementation : 3/5
Author rated this task as the 5/6th hardest task out of 11 tasks. Yet it has 2 solves in contest.

Link

English by 300iq

Statement

Wang Xiuhan has an initially empty undirected graph on $1 \le n \le 3e5$ vertices.
Each vertex $i$ has a weight $0 \le w_i \le 1e6$
Also, he has $1 \le m \le 3e5$ tuples $(a_i,b_i,s_i)$, where $1 \le a_i,b_i \le n$, $a_i \neq b_i$, and $0 \le s_i \le 1e6$
After that, he starts the following process:
- If there is no such i that ai and bi lie in different connected components of the graph and (total weight of vertices in the component of $a_i$) + (total weight of vertices in the component of $b_i$) ≥$s_i$, end the process.
- Otherwise, choose the smallest such $i$, add an edge between $a_i$ and $b_i$ to the graph, write this $i$ in the notepad, and repeat the process (but now on the larger graph).
After the process was completed, a misfortune happened... Someone stole his notepad! Can you help him restore all numbers efficiently?

Solution

Let's call a tuple ready if the sum of weights of the connected components of its two endpoints are $\ge s$ (and the tuple isnt already used). We dont have to care about whether $a$ and $b$ are in the same component because we can just skip it if they are. Obviously if a tuple is ready it will always be ready. Basically, if we can maintain the set of tuples that are ready we can solve the problem.
An important fact is that $a+b \ge s$ implies that $a \ge \frac{s}{2}$ or $b \ge \frac{s}{2}$. Let's call a certificate to be that the connected component containing $x$ has total weight $< y$. Call the certificate $(x,y)$. So for each tuple we can make certificates $(a,\frac{s}{2})$ and $(b,\frac{s}{2})$. As long as the certificates aren't broken, we don't have to worry about this tuple.
So, what do we do when the certificates are broken? Let's say the sum of weights for component of $a,b$ is $u,v$ respectively. so we will ditch our old certificates and make new ones, that is $(a,u+\frac{s-u-v}{2})$ and $(b,v+\frac{s-u-v}{2})$. The important observation is that each time $\frac{s-u-v}{2}$ is reduced by a half, so you only need to renew the certificates $O(logS)$ times for each tuple. So we renew our certificates until the tuple is ready.
So now, we have to maintain operations of:
1)Join two components
2)Find all broken certificates and renew them.
Which is standard small-to-large exercise. Complexity is $O(NlgNlgS)$.

Comments

Very good problem... I like this idea very much. I always thought amortized $logC$ ideas are not possible to hide but I missed this trick completely. I have also stolen this idea and make it on a segment so if you don't like trees you can join this group and try that problem instead.