P4297 [NOI2006] 网络收费

noi2006 day1t1

网络已经成为当今世界不可或缺的一部分。每天都有数以亿计的人使用网络进行学习、科研、娱乐等活动。然而，不可忽视的一点就是网络本身有着庞大的运行费用。所以，向使用网络的人进行适当的收费是必须的，也是合理的。 MY 市NS 中学就有着这样一个教育网络。网络中的用户一共有$2^N$个，编号依次为1, 2, 3, …, $2^N$。这些用户之间是用路由点和网线组成的。用户、路由点与网线共同构成一个满二叉树结构。树中的每一个叶子结点都是一个用户，每一个非叶子结点（灰色）都是一个路由点，而每一条边都是一条网线（见下图，用户结点中的数字为其编号）。  MY 网络公司的网络收费方式比较奇特，称为“ 配对收费 ”。即对于每两个用户$i, j (1≤i < j ≤2^N )$ 进行收费。由于用户可以自行选择两种付费方式A、B中的一种，所以网络公司向学校收取的费用与每一位用户的付费方式有关。该费用等于每两位不同用户配对产生费用之和。 为了描述方便，首先定义这棵网络树上的一些概念： - 祖先：根结点没有祖先，非根结点的祖先包括它的父亲以及它的父亲的祖先； - 管辖叶结点：叶结点本身不管辖任何叶结点，非叶结点管辖它的左儿子所管辖的叶结点与它的右儿子所管辖的叶结点； - 距离：在树上连接两个点之间的用边最少的路径所含的边数。 对于任两个用户$i, j (1≤i

无

无

【样例说明】 将 1 号用户的付费方式由B 改为A，NS 中学支付给网络公司的费用达到最小。 【数据范围】 40%的数据中$N≤4$； 80%的数据中$N≤7$； 100%的数据中$N≤10$，$0≤F_{i, j}≤500$，$0≤C_i≤500 000$。