比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
yrtiop | AAAWWWWWWW | 0.000 s | 0.00 MiB | 30 |
遥时_彼方 | AAAEEEEEEE | 1.465 s | 9.96 MiB | 30 |
ZRQ | AAATTTTTTT | 7.133 s | 8.79 MiB | 30 |
HeSn | TTTEEEEEEE | 4.336 s | 13.45 MiB | 0 |
lavey | TTTTTTTTTT | 10.000 s | 43.88 MiB | 0 |
给出一颗 $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$ 之间有一条边。
一个整数,表示所有点对之间的最少边数之和。
4 1 2 1 3 1 4
6
4 1 2 2 3 3 4
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)