← 返回题单

题单练习最近公共祖先

← 上一题下一题 →

A6252 | $机房$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

这天，小明在机房学习。 他发现机房里一共有 $n$ 台电脑，编号为 $1$ 到 $n$，电脑和电脑之间有网线连接，一共有 $n-1$ 根网线将 $n$ 台电脑连接起来使得任意两台电脑都直接或者间接地相连。 小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连，而信息在网线中的传播时间可以忽略。比如如果某台电脑用网线直接连接了另外 $d$ 台电脑，那么任何经过这台电脑的信息都会延迟 $d$ 单位时间（发送方和接收方也会产生这样的延迟，当然如果发送方和接收方都是同一台电脑就只会产生一次延迟）。 小明一共产生了 $m$ 个疑问：如果电脑 $u_{i}$ 向电脑 $v_{i}$ 发送信息，那么信息从 $u_{i}$ 传到 $v_{i}$ 的最短时间是多少?

输入格式

输入共 $n+m$ 行，第一行为两个正整数 $n, m$。 后面 $n-1$ 行，每行两个正整数 $x, y$ 表示编号为 $x$ 和 $y$ 的两台电脑用网线直接相连。 后面 $m$ 行，每行两个正整数 $u_{i}, v_{i}$ 表示小明的第 $i$ 个疑问。

输出格式

输出共 $m$ 行，第 $i$ 行一个正整数表示小明第 $i$ 个疑问的答案。

输入输出样例

输入 #1

输出 #1

5
6
1

C++ 编辑器

输入

输出