题目内容

小红有一颗 $n$ 个结点的二叉树，根结点为 $1$。

定义树上一个点的坐标为$(x_i,y_i)$，根结点的坐标为$(0,0)$。

题解

题面描述

给定一棵有根的二叉树，树共有 $n$ 个结点，根结点编号为 $1$。每个结点的坐标通过其父结点的坐标确定。根结点的坐标为 $(0,0)$，每个结点的坐标依赖于其父结点的坐标以及该结点是父结点的左儿子还是右儿子。如果一个结点为父结点的左儿子，则其坐标为 $(a-1, b-1)$，如果该结点为父结点的右儿子，则其坐标为 $(a+1, b-1)$。一棵树上每一对结点的曼哈顿距离定义为它们的坐标差的绝对值之和，即

现在给定一个二叉树，树上有若干个查询，每次查询给定两个结点，要求输出这两个结点的树上曼哈顿距离。