比赛场次 515
比赛名称 EYOI暨SBOI暑假快乐赛5th
比赛状态 已结束比赛成绩
开始时间 2022-06-29 08:30:00
结束时间 2022-06-29 12:00:00
开放分组 全部用户
注释介绍 EYOI暨SBOI2022暑假的第五场比赛!
暑假热身赛第五,题都不是很难哦!
细心审题,尽力拿到可以拿到的分数!
注意题目难度不是按照题目编号依次递增!
题目名称 Sergey and Subway
输入输出 Sergeyas.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravataryrtiop AAAWWWWWWW 0.000 s 0.00 MiB 30
Gravatar遥时_彼方 AAAEEEEEEE 1.465 s 9.96 MiB 30
GravatarZRQ AAATTTTTTT 7.133 s 8.79 MiB 30
GravatarHeSn TTTEEEEEEE 4.336 s 13.45 MiB 0
Gravatarlavey TTTTTTTTTT 10.000 s 43.88 MiB 0

Sergey and Subway

★★   输入文件:Sergeyas.in   输出文件:Sergeyas.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

给出一颗 $N$ 个节点的树,现在我们在原图中每个不直接连边但是中间只间隔一个点的两个点之间连一条边。

比如在原图中 $u$ 与 $v$ 连边,$v$ 与 $w$ 连边,但是 $u$ 与 $w$ 不连边,这时候我们就需要连一条 $u$ 与 $w$ 的边。

现在我们需要求出新图中每一个点对 $(i,j)\ (1 \le i \le j \le N)$ 的经过的最少的边数和。

【输入格式】

第一行包含一个整数 $N$,表示树的节点数量。

接下来 $N-1$ 行,每行两个整数 $x,y$,表示节点 $x,y$ 之间有一条边。

【输出格式】

一个整数,表示所有点对之间的最少边数之和。

【样例输入1】

4
1 2
1 3
1 4

【样例输出1】

6

【样例输入2】

4
1 2
2 3
3 4

【样例输出2】

7

【样例说明】

第一组样例中没有新边,不做解释。

第二组样例中,建出新边后,得到:

$(1,2)$ 之间最少 $1$ 条边,$(1,3)$ 之间最少 $1$ 条边,$(1,4)$ 之间最少 $2$ 条边(即 $1\to 3,3 \to 4$)。

$(2,3)$ 之间最少 $1$ 条边,$(2,4)$ 之间最少 $1$ 条边。

$(3,4)$ 之间最少 $1$ 条边。

故答案为 $1+1+2+1+1+1=7$。

【数据规模与约定】

对于 30% 的数据,$1 \le n \le 10^3$。

对于 100% 的数据,$1 \le n \le 2 \times 10^5$。

【来源】

Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2)