CF288D Polo the Penguin and Trees

小企鹅 Polo 得到了一棵树——即一个无向连通无环图，包含 $n$ 个节点以及 $n-1$ 条边。我们假设树上的节点编号为 $1$ 到 $n$ 的整数。 今天，Polo 想知道怎样计算没有公共节点的路径对数。更正式地说，他想找到有多少组四元组 $a, b, c, d$ 满足： - $1 \leq a < b \leq n$； - $1 \leq c < d \leq n$； - 没有任何一个节点同时位于从节点 $a$ 到节点 $b$ 的最短路径和从节点 $c$ 到节点 $d$ 的最短路径上。 两节点间的最短路径指的是边数最少的路径。 请你帮 Polo 解决这个问题。

第一行包含一个整数 $n$ $(1 \leq n \leq 80000)$，表示树的节点数。接下来的 $n-1$ 行每行包含一对整数 $u_i$ 和 $v_i$ $(1 \leq u_i, v_i \leq n; u_i \neq v_i)$，表示第 $i$ 条树边连接的两个节点。 保证给定的图结构是一棵树。

输出一行一个整数，表示满足条件的四元组数量。 请勿在 C++ 中使用 %lld 读写 64 位整数。建议使用 cin、cout 流或 %I64d。

由 ChatGPT 5 翻译