P3728.第2题-树上曼哈顿距离
题目内容
小红有一棵n个结点的二叉树，根结点为1。
定义树上一个点的坐标为(xi,yi)，根结点的坐标为(0,0)。
一个结点若有两个子结点，那么我们称编号较小的结点为左儿子，编号较大的为右儿子，若只有一个结点，默认其为左儿子。
若一个结点的父结点坐标为(a,b)，如果该结点为父结点的左儿子，那么此结点的坐标为(a−1,b−1)，如果该结点为父结点的右儿子，那么该结点的坐标为(a+1,b−1)。
定义两点的树上曼哈顿距离为∣x1−x2∣+∣y1−y2∣。
现在小红会提出若干个询问，每次给出两个点，请你回答两点的树上曼哈顿距离。
输入描述
第一行两个整数n,q(1≤n,q≤105)，表示结点个数和询问次数。
接下来n−1行，每行2个整数u,v(1≤u,≤n,u=v),表示u,v之间存在一条无向边。
接下来q行，每行两个整数x,y(1≤x,y≤n)，表示询问的点对。
输入保证是一棵二叉有根树。
输出描述
q 行，每行一个整数，两个点的树上曼哈顿距离。
样例1
输入
5 2
1 2
2 3
2 4
3 5
1 5
3 1
输出
6
4
说明
五个点的坐标分别为
(0,0),(−1,−1),(−2,−2),(0,−2),(−3,−3)。
