P7434 「MCOI-04 / AC6-M09」Heavy Command Cruiser

这是一个作战部署命令。 我们已经从国家安全局获得了有关敌方重型指挥巡洋舰的部分机密情报。 敌方巡航机的正式名称已被确认为 P-1112 Aigaion。 空中舰队中包含一种 Kottos 中型巡航机负责电子支援，还有一种 Gyges 中型巡航机负责近程防空。 Aigaion，作为指挥机，负责一切与巡航导弹相关的事务。 在获得这些情报之后，我们可以草拟一个摧毁 Aigaion 的计划。 仔细听好了。 Aigaion 只能在机体前部接受空中加油。 多架加油机必须同时处在 Aigaion 前方才能进行加油作业。 当加油机在 Aigaion 前部进行加油时，Aigaion 的雷达探测能力会暂时削弱。 这里就是关键点了。 Aigaion 在进行加油时，其雷达基本完全无法探测在其前方飞行的物体。 如果你们能维持在一个固定航线并在一个特定高度上飞行，你们就能在不被敌军发现的情况下，从空中接近 Aigaion。 所以我们解决掉这只怪物的最佳时机就是它进行空中加油的时候。 Aigaion 的预定航线图也包含在这份情报中。 简报结束后，我们将在机库再次检查航线图。 快去准备吧。 ………… Garuda 队，交战！ $$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 09} \\\Large\text{Heavy Command Cruiser}\\\tiny -\ The\ Dead\ Sea\ -$$ 

在平面上给定一棵有根树，树根为 $1$，根的深度为 $0$。 对于深度为 $x$ 的节点，其 **纵坐标** 为 $n-x+1$。 对于一个节点的所有子节点，**从左到右按照编号升序排列**。每条边都是一条 **连接两个点的线段**。 每一个叶子节点都有一条 **平行于 $y$ 轴且向 $y$ 轴负方向无限延伸的射线**，根节点有一条 **平行于 $y$ 轴且向 $y$ 轴正方向无限延伸的射线**。 每个线段或射线带一个权值。 **任意两条线段或射线只在树的节点处相交。** 如果你不理解这个树是怎么画的，可以阅读样例 1 解释。 给定 $q$ 组 $u,v$，你现在要从点 $u$ 开始在平面上自由移动，但是你不能经过除 $u,v$ 以外的任何一个点，且每经过一条线段或射线就会产生其对应的权值的代价。 你的目标是移动到点 $v$，你需要求出移动过程产生的最小代价。

无

无

idea：Sol1，solution：dengyaotriangle & Sol1 & Guoyh，code：Sol1，data：Sol1 对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^5$，$1\leq q\leq 5\times 10^6$，$1\leq f_i