在DoubleDog成功辨别出来种族之后,旁边出现了一群小黄鸭和一只wangyisong1996。
wangyisong1996拦住了这些DoubleDog,说他可以给他们以帮助,但是他们需要先做出来一道题。
wangyisong1996有一颗
他已经实现了除了树链剖分以外的其他所有东西,现在他想要知道最优的一种树链剖分方案。
树链剖分的时间复杂度如下:
定义树上的一个树链剖分为一种将边集划分为重边和轻边的方法使得每个节点和他的儿子之间最多只有一条重边。
在下面的表示中,我们将重边称为
定义树上的
对于一个长度为
对于一个长度为
对于一个01串,我们有
例如:
对于一个轻重边划分方案
现在wangyisong1996想要知道所有可行的树链剖分方案中,时间复杂度(也就是O(方案))最小的值是多少
输入格式
第一行一个正整数
接下来
输出格式
一行一个数字,表示答案。
样例一
input
7 1 2 2 3 2 4 2 5 2 6 2 7
output
11
explanation
将边
此时
样例二至样例四
见样例数据下载。
限制与约定
Subtask 1 (5 分):
Subtask 2 (15 分):
Subtask 3 (15 分):
Subtask 4 (30 分):
Subtask 5 (35 分):
时间限制: