A79552.树

青蛙有 $k$ 棵树，编号为 $1\sim k$。每棵树都有 $n$ 个节点，编号为 $0\sim n-1$。

定义函数 $\operatorname{F}(t,x,y)$，表示第 $t$ 棵树上从点 $x$ 到点 $y$ 的简单路径上的点的编号的 $\operatorname{mex}$ 值。

现在青蛙想知道 $k$ 棵树到底有多呱呱，所以想请你求出下面式子的答案，用来表示 $k$ 棵树的总呱呱值：

$$\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}\max_{t=1}^{k} \operatorname{F}(t,x,y)$$

定义 $\operatorname{mex}(S)$ 表示自然数集合 $S$ 中最小的没有出现过的自然数。

第一行两个正整数 $n,k$ 表示共有 $k$ 棵树，每棵树大小为 $n$。

接下来 $k \times (n-1)$ 行，每 $n-1$ 行表示一棵树。其中每行两个非负整数 $u,v$ 表示 $u$ 与 $v$ 之间有一条无向边连接。

输出一行一个数，表示这 $k$ 棵树的总呱呱值。

输入文件名： cute.in 输出文件名 cute.out

对于所有数据，保证 $3\le n\le 3\times 10^5,\; 1\le k\le 3,\; 0\le u,v < n$，且输入数据构成 $k$ 棵树。

T3相关文件下载

子任务编号	$n \le$	$k$	特殊性质	分值
1	$3$	$\le 3$	无	5
2	$30$	$\le 3$	无	5
3	$3000$	$\le 3$	无	10
4	$3\times 10^5$	$=1$	无	15
5	$3\times 10^5$	$=2$	有	15
6	$3\times 10^5$	$=2$	无	15
7	$3\times 10^5$	$=3$	有	15
8	$3\times 10^5$	$=3$	无	20

特殊性质：保证数据随机生成，生成方式为：随机生成一个 $0\sim n-1$ 的排列，除了第一个点外，每个点随机向前面的一个点连边。