P8260 [CTS2022] 燃烧的呐球

**警告：滥用本题卡评测者将被封号。**

已知 $n$ 个顶点的有根树，以及 $m$ 个二元组 $(x_i,y_i)$，其中 $x_i,y_i$ 是树的顶点。 对于树的顶点 $a,b$，定义 $D(a,b)$ 为：在以 $a$ 为根的子树中，但不在以 $b$ 为根的子树中的顶点个数。 你需要求出以这些二元组为顶点的完全图的最小生成树，其中 $(x_i,y_i)$ 和 $(x_j,y_j)$ 之间的边权是 $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$。

无

无

样例解释： 最小生成树包含边 $(1,4,1),(2,3,3),(2,4,3)$，三元组表示第一个二元组的编号，第二个二元组的编号，边权。边权和为 $7$。 数据范围： 对于 $10\%$ 的数据，满足 $1\le n,m\le 1000$。 对于另外 $10\%$ 的数据，满足 $1\le m\le 2\times 10^4$。 对于另外 $10\%$ 的数据，满足 $1\le m\le 5\times 10^4$。 对于另外 $20\%$ 的数据，满足 $m=n^2$，且每个二元组互不相同。 对于另外 $10\%$ 的数据，满足对任意 $i=2\cdots n$，$f_i=i-1$。 对于另外 $10\%$ 的数据，满足对任意 $i=2\cdots n$，$f_i=1$。 对于 $100\%$ 的数据，满足 $1\le n\le 10^6,1\le m\le 10^5$。对任意 $i=1,2,\dots n-1$，满足 $1\le f_{i+1}