给定一棵 n 个节点树。节点 1 为树的根节点,对于所有其他节点 i,它们的父节点编号为 floor(i/2) (i 除以 2 的整数部分)。在每个节点 i 上有 a[i] 个房间。此外树上所有边均是边长为 1 的无向边。 树上一共有 m 只松鼠,第 j 只松鼠的初始位置为 b[j],它们需要通过树边各自找到一个独立的房间。请为所有松鼠规划一个移动方案,使得所有松鼠的总移动距离最短。
格式:
输入:
- 输入共有三行。
- 第一行包含两个正整数 n 和 m,表示树的节点数和松鼠的个数。
- 第二行包含 n 个自然数,其中第 i 个数表示节点 i 的房间数 a[i]。
- 第三行包含 m 个正整数,其中第 j 个数表示松鼠 j 的初始位置 b[j]。
输出:
- 输出一个数,表示 m 只松鼠各自找到独立房间的最短总移动距离。
示例:
输入:
5 4
0 0 4 1 1
5 4 2 2
输出:4
解释:前两只松鼠不需要移动,后两只松鼠需要经节点 1 移动到节点 3
提示: