题面 下发文件

题目描述

给定一棵包含 $n$ 个点的树。$\forall 1\le u,v\le n$ ，定义 $dis(u,v)$ 为 $u$ 到 $v$ 的简单路径上的边数。

$\forall 1\le u,v\le n,u\neq v$ ，我们称 $u$ 喜欢 $v$ ，当且仅当 $\forall 1\le w\le n,w\neq v$ 都满足 $dis(u,w)\neq dis(u,v)$ 。

你需要回答 $q$ 次询问。

每次询问给定 $l_1,r_1,l_2,r_2$ ，你需要回答有多少有序对 $(u,v)$ 满足：

$u\in [l_1,r_1],v\in [l_2,r_2]$ ，且 $u$ 喜欢 $v$ 。

输入格式

第一行包含两个整数 $n,q$ 。

接下来 $n-1$ 行，每行包含两个整数 $u,v$ ，代表这棵树的一条边。

接下来 $q$ 行，每行包含四个整数 $l_1,r_1,l_2,r_2$ ，代表一次询问。``

输出格式

对于每次查询，输出一行一个整数，表示这次查询的答案。

样例

样例 1 输入

10 10
1 8
8 9
9 2
2 6
1 4
2 5
5 10
6 7
1 3
2 2 9 10
6 7 1 6
8 10 4 9
5 8 7 10
3 4 8 10
2 10 6 7
7 10 10 10
3 4 2 10
2 10 5 7
6 8 1 9

样例 1 输出

0
4
1
0
2
1
0
4
2
4

样例 2~5

见下发文件。

数据范围

所有数据满足：$1\le n,q\le 10^5$ ， 保证输入给出的是一棵树。

对于每次询问，$1\le l_1\le r_1\le n,1\le l_2\le r_2\le n$ 。

特殊性质 A ：给出的树所有节点度数都 $\le 2$ 。

特殊性质 B：$q=1$ 。

特殊性质 C：所有查询都满足 $l_2=1,r_2=n$ 。

特殊性质 D：给定的树是随机生成的，具体的，我们会生成一棵以 $1$ 为根的树，$\forall 2\le i\le n$ ，$i$ 的父亲在 $[1,i-1]$ 间均匀随机。之后会将编号重新随机排列。