2698 问题 F: 蓝桥杯2022年第十三届决赛真题-机房

时间限制: 1s 内存限制: 256MB 提交: 2137 解决: 438
题目描述

这天,小明在机房学习。

他发现机房里一共有 n 台电脑,编号为 1 到 n,电脑和电脑之间有网线连接,一共有 n − 1 根网线将 n 台电脑连接起来使得任意两台电脑都直接或者间接地相连。

小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连,而信息在网线中的传播时间可以忽略。比如如果某台电脑用网线直接连接了另外 d 台电脑,那么任何经过这台电脑的信息都会延迟 d 单位时间 (发送方和接收方也会产生这样的延迟,当然如果发送方和接收方都是同一台电脑就只会产生一次延迟)。

小明一共产生了 m 个疑问:如果电脑 ui 向电脑 vi 发送信息,那么信息从 ui 传到 vi 的最短时间是多少?

输入

输入共 n + m 行,第一行为两个正整数 n, m。

后面 n − 1 行,每行两个正整数 x, y 表示编号为 x 和 y 的两台电脑用网线直接相连。

后面 m 行,每行两个正整数 ui , vi 表示小明的第 i 个疑问。

输出
输出共 m 行,第 i 行一个正整数表示小明第 i 个疑问的答案。
样例输入
4 3
1 2
1 3
2 4
2 3
3 4
3 3
样例输出
5
6
1
提示

这四台电脑各自的延迟分别为 2, 2, 1, 1。

对于第一个询问,从 2 到 3 需要经过 2, 1, 3,所以时间和为 2 + 2 + 1 = 5。

对于第二个询问,从 3 到 4 需要经过 3, 1, 2, 4,所以时间和为 1+2+2+1 = 6。

对于第三个询问,从 3 到 3 只会产生一次延迟,所以时间为 1。

对于 30% 的数据,保证 n, m ≤ 1000;

对于 100% 的数据,保证 n, m ≤ 100000 。

比赛公告


请对本次比赛进行一些描述,公告内容应当包含:
比赛的创办者或组织;
本次比赛的目的或意义;
本次比赛的考点、语言或类型;或其他注意事项及描述等。
至少保证30个汉字长度。