CF804D Expected diameter of a tree

Pasha 是个好学生，也是 MoJaK 最好的朋友之一。他总是有思考的问题。今天他们讨论了如下问题。 给你一片森林（无环无向图），共有 $n$ 个顶点和 $m$ 条边。你需要回答 $q$ 个询问。每次询问给出两个顶点 $v$ 和 $u$。设 $V$ 是包含 $v$ 的连通块的所有顶点集合，$U$ 是包含 $u$ 的连通块的所有顶点集合。我们从 $V$ 中任选一个顶点 $a$，从 $U$ 中任选一个顶点 $b$，添加一条连接 $a$ 和 $b$ 的边，得到一个新的连通块，并计算新连通块的直径值 $d$。如果得到的新连通块是树，则 $d$ 为新连通块的直径；否则 $d=-1$。如果我们从 $V$ 和 $U$ 中分别随机选择 $a$ 和 $b$，那么 $d$ 的期望值是多少？ 你能帮助 Pasha 解决这个问题吗？ 连通块的直径定义为连通块内任意两点间路径上的最大最短距离。两个顶点之间的距离是两点之间的最短路径上的边数。 注意，询问只是模拟加边，并不会真的改变初始森林结构。

第一行为三个整数 $n$，$m$，$q$（$1\leq n,m,q\leq 10^{5}$），分别表示图的顶点数、边数和询问数。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1\leq u_i,v_i\leq n$），表示在 $u_i$ 和 $v_i$ 之间有一条边。 保证所给图是一片森林。 接下来的 $q$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1\leq u_i,v_i\leq n$），为第 $i$ 次询问给定的两个顶点。

对于每个询问，输出对应的 $d$ 的期望值。 你的答案将被认为是正确的，当且仅当其绝对误差或相对误差不超过 $10^{-6}$。假设你的答案为 $a$，标准答案为 $b$，检查器会判定当 $|a-b|\leq 10^{-6} \max(1,|b|)$ 时你的答案是正确的。

在第一个样例中，顶点 $1$ 和 $3$ 在同一个连通块内，因此第一个询问的答案为 $-1$。对于第二个询问，有两种加边方式：可以加边 $1-2$ 或 $2-3$，两种方式合并后新连通块的直径都是 $2$，所以答案是 $2$。 在第二个样例中，第一个询问答案显然是 $-1$。第二个询问有三种加边方式：加边 $1-2$ 或 $1-3$ 时新直径为 $3$，加边 $1-4$ 时新直径为 $2$。所以答案是 $\frac{3+3+2}{3}=2.666666...$。 由 ChatGPT 5 翻译