蓝桥杯国赛B题：结合树上差分与LCA的算法设计

[蓝桥杯 2022 国 B] 机房

题目描述

这天，小明在机房学习。

他注意到机房内共有n台计算机（即机器），这些机器的编号从1开始一直到n。此外，在这些机器之间通过网络线路进行了互联配置：每台机器都与其他机器通过网络线路相接，并且这些网络线路总共提供了n-1条连接路径来联结所有的计算机（即无论是直接相接还是通过其他设备中间传递信息）。

小明发现每台电脑在转发、发送或接收信息所需的时间，则是由该台电脑与之直接相连的其他多少台电脑的数量所决定的；而信息在网线中的传输时间则可忽略不计。例如：如果某台电脑通过网线直接连接到了其他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