小红的树上路径查询（hard）

题号：NC281352
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题和 $hard$ 难度的区别是，询问的次数有多次！

小红拿到了一棵树，她有多次询问，每次询问输入一条简单路径 $x,y$ ，她想知道树上所有节点到该路径的最短路之和是多少，你能帮帮她吗？

定义节点到路径的最短路为：节点到路径上所有点的最短路中，值最小的那个。特殊的，如果节点在路径上，则最短路为0。

简单路径：从树上的一个节点出发，沿着树的边走，不重复地经过树上的节点，到达另一个节点的路径。

第一行输入两个正整数，代表节点数量和询问次数。
接下来的行，每行输入两个正整数，代表节点和节点有一条边连接。
接下来的行，每行输入两个正整数，代表一次询问。

输出行，每行输出一个整数，代表询问的答案。

示例1

复制

复制

1
2