F 年少有为

题号：NC223211
时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$n \times n$ 的平面上有 n 个点，保证点在一定限制下随机生成且互不相同，生成点的随机方式附在输出格式中。

用 n - 1 条边将它们链接成一棵树。

定义 ${\rm dist}(i,j)$ 为树上点 i 和 j 之间最短简单路径的边数。

定义 ${\rm diam}(x,y,r,c)$ 为坐标系上左下角为 (x, y)，右上角为 (r, c) 的矩形中，所有点对两两间 ${\rm dist}(i,j)$ 的最大值。矩形可能为空。

试求 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\operatorname{diam}(x_i, y_i, x_j, y_j)$ 。

输入描述:

第一行两个数 n，B。 $(1 \le n \le 10^5, B=\min(n,500))$

接下来给出 n 行，每行两个数 x，y，表示每个点的坐标。

接下来给出 n - 1 行，每行两个数 u，v，表示边。

输出描述:

一行，表示答案。

随机方式如下：定义 ，有所有点在集合  中均匀随机生成。

示例1

输入

复制

输出

复制