清华集训2015 UOJ155 遥远的星系

一道好题...论我的智商是如何被碾压的...

题意

有一个无向图，对于每条边[tex](u,v,w)[/tex]，从[tex]u[/tex]走到[tex]v[/tex]要花费[tex]w[/tex]的代价，反之花费[tex]-w[/tex]的代价。

强制在线，要求支持添加一条边，询问两个点之间是否存在一条路径(不一定是简单路径)，总花费为给定值。

题解

考虑直接用并查集维护，对于不连通的连通块，我们直接用并查集合并，每个节点记录到根的路径长度和。

如果加入了一条连通块内的边，我们对于每一个连通块，记录所有的如果用非树边代替树边导致的费用差的gcd(我语死早别吐槽...)。

然后我们发现对于一个询问，如果直接从树边走过去不为答案，我们必须要通过非树边绕圈。而绕圈的最低花费是这些非树边的gcd...

于是这题就做完了...

想了半天完全不会做，一看别人的程序就明白了...我的智商好低T_T

所以说做这种题的重点是不被题目吓到？[tex]10^6[/tex]个操作的题似乎也只有并查集跑得过去？