← 返回比赛

已结束【提高组】GESP“飞翔杯”第四届季度赛

← 上一题下一题 →

A5252 | $树$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

青蛙有 $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$ 棵树的总呱呱值。

输入输出样例

输入 #1

3 1
0 1
1 2

输出 #1

输入 #2

输出 #2

输入文件名： 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$无52$30$$\le 3$无53$3000$$\le 3$无104$3\times 10^5$$=1$无155$3\times 10^5$$=2$有156$3\times 10^5$$=2$无157$3\times 10^5$$=3$有158$3\times 10^5$$=3$无20 特殊性质：保证数据随机生成，生成方式为：随机生成一个 $0\sim n-1$ 的排列，除了第一个点外，每个点随机向前面的一个点连边。

C++ 编辑器

输入

输出