如下图所示,比特之地是在一颗土豆地雷发达的根系上建立的。
起初这些根系只是越来越多,在地下形成了一个复杂的网络。形式上,这些根系形成了一棵向下的树。
当比特族的祖先地底漂泊到这里的时候,决定在这里建立比特的家园,按照树的顺序在对应的位置修砌了房屋。这些位置可以被视作树上的节点,节点之间由根系相连,可以视作树中的边。特别地,最接近地面的节点唯一,且被称为根节点。
比特族的祖先将比特的家园建造得井井有条。具体地,这棵树满足以下性质:
一条边连接的两个节点中,较深的节点的编号更大。
以每个点为根的子树的编号都是一段连续的区间。
对于同一层的点,左边的点编号比右边的小。
时至今日,比特们通上了信息高速路。比特国网络服务公司在原有的根系,也就是树边上铺设了光纤,这样所有节点的比特们都可以通信。
为了使得通信网络更加稳固,公司又在比特之地中左右相邻的同层节点之间拉好光纤(图中棕色边)。这里一个节点的层数是指它到根节点所经过的边数。
现在,苦读通信工程的你接到了帮助比特国估算网络延迟的任务。
形式化题意: