问题2965--路径计数(paths)

2965: 路径计数(paths)

时间限制: 2 Sec  内存限制: 512 MB
提交: 4  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一张n(n≤250000)个点的无向连通图,共有n-1条边,即给定的是一棵树。
对于树上的任意两个点,定义P(u,v)为点u和点v之间的最短路上的所有点的集合(包括u和v)。
现在有Q(Q≤300000)个询问,每次询问给出两个点u,v,问有多少个点对a,b(a≤b),满足集合P(u,v)和集合P(a,b)有且仅有一个公共点。换句话说,要问有多少个点对a,b(a≤b),使得a, b之间的最短路和u, v之间的最短路恰好相交于一个点。

输入

第一行两个正整数n,Q。
接下来n-1行每一行两个正整数x,y,表示x,y之间有一条边。
接下来Q行每行两个正整数u,v,表示一个询问。

输出

对于每个询问,输出一行答案。

样例输入 Copy

6 2
1 2
1 3
1 4
2 5
2 6
4 5
1 3

样例输出 Copy

6
9

提示

来源/分类