一道好题。

这是一个树形结构，我们可以先拍成 $dfn$ 序，然后对于每个星球，本质上就是在其子树内区间再 删去一些小子树 所构成的一些区间，因为最多 $n$ 个操作，所以区间最多 $\mathcal{O}(n)$ 个，线段树分治，把这些区间插入，然后我们考虑如何求答案。

$y,z$ 是没用的，最终答案即为 $(x_0 - x)^2 + c$，拆开得 $- 2x_0x + {x_0}^2 + x^2 + c$。

我们考虑斜率优化，在看这个式子 $s = - 2x_0x + {x_0}^2 + x^2 + c$，移项得 $x^2 + c = 2x_0x - {x_0}^2 + s$，即点 $(x,x^2 + c)$ 斜率为 $2x_0$，维护下凸包即可，若二分则复杂度是 $\mathcal{O}(n\log^2{n})$，只需将 $x$ 与斜率 $x_0$ 都从小到大排序，我们可以利用单调栈达成 $\mathcal{O}(n\log{n})$ 的复杂度。

首先可以不是简单路径，这启示我们用并查集，但 $a,b$ 的二维限制有些不可做，我们可以先想暴力，对于每个询问只需将所有 $a_i \leq a$ 且 $b_i \leq b$ 的所有边加入并查集，并维护最大 $a,b$ 值，判断 $u,v$ 是否在一个联通块内，且最大值即为 $a,b$，这样可以 $\mathcal{O}(mq\log{n})$。

限制太特殊了，我们考虑分块，首先将所有边按照 $a$ 排序后分块，每个询问离线下来后把其放到尽量右块内，使所有其左边的块的 $a$ 值都小于等于它，然后我们枚举每个块，将该块询问先按照 $b$ 排序，再将前面的块按照 $b$ 排序，双指针加边即可。

对于在该块内的边，我们暴力枚举加边，枚举后撤销这些操作，所以 并查集不能路径压缩，只能按秩合并。

复杂度 $\mathcal{O}(qB\log{n} + \frac {m^2} B \log{n})$，取 $B = \sqrt{m}$ 得复杂度为 $\mathcal{O}((q + m)\sqrt{m}\log{n})$。

但是貌似 $B = \sqrt{m\log{n}}$ 跑的最快 : )。

首先我们假设两条边 $(u1,v1)$，$(u2,v2)$ 中间未选择断边，则我们可以考虑 DP，设 $f_i$ 表示 必须选 $(fa_i,i)$ 这条边时在其子树内走可以得到的最大贡献，则任意一点 $v$ 在其子树内，则有转移方程 $f_i = \max\limits_{v \in son(i)} f_v + size_v \times (size_u - size_v)$，这东西可以用 李炒熟 维护，对于树形结构可以用 李超树合并 解决子树问题。

但是这显然没完，上述所求的只是在一条链 从子树到祖先 上的路径，然后我们考虑在某个点合并两条链，假设合并两点 $u,v$，则需要再减去重复的贡献 $size_u \times size_v$，所以我们求得答案即为 $f_u + f_v - size_u \times size_v$ 的最大值，显然也可以用 李焯书，然后考虑如何合并，显然可以用 淀粉质，复杂度是 $\mathcal{O}(n\log^2{n})$ 的，但巨大长代码。

知周所众，dsu on tree 是可以代替一些淀粉质的，所以我们考虑用 dsu on tree，考虑每个点 $x$，保存其 重儿子 的李超树，其余节点暴力查询答案，然后进行 李焯书贺兵 即可，复杂度也是 $\mathcal{O}(n\log^2{n})$，但较好写，常数也小。

首先我们考虑如何求每个点的贡献，可以发现只有最后一次经过某点的时间是有用的，我们可以考虑 最少失去的法力值，设其为 $w$ ，则答案即为 $s \times \sum m - w$，$n$ 较小，考虑状压 DP，因为询问规定了最终点，所以一维是不行的，设 $f_{i,j}$ 表示已经最后一次经过状态 $i$ 中的点，且当前在 $j$ 位置的最小答案，则有状态转移方程：

$$f_{i,j} = \min {f_{la,k} + d_{k,j} \times s_{la}}$$

其中 $d_{i,j}$ 表示 $i$ 到 $j$ 的最短路，$s_{i}$ 表示状态 $i$ 中所有节点的 $m$ 和。

然后对于答案，即为 $ans = \underline{s_{i}}_k \times \underline{s}_x + (\underline{-f_{i,j}}_b)$，显然可以 李焯书 解决。

复杂度 $\mathcal{O}(2^nn^2 + 2^nn\log{V} + q\log{V})$，当然也可以维护凸包，但是瓶颈不在这，复杂度差不多。

#include<bits/stdc++.h>

using namespace std;

int main()

{ <

........................................................................

该题解等待再次审核

#include<bits/stdc++.h>

using names

........................................................................

该题解等待再次审核