UOJ Logo Universal Online Judge

UOJ

#462. 新年的小黄鸭

附件下载 统计

在DoubleDog成功辨别出来种族之后,旁边出现了一群小黄鸭和一只wangyisong1996

wangyisong1996拦住了这些DoubleDog,说他可以给他们以帮助,但是他们需要先做出来一道题。

wangyisong1996有一颗n个节点的有根树,根节点为1,他想在这颗树上跑树链剖分。

他已经实现了除了树链剖分以外的其他所有东西,现在他想要知道最优的一种树链剖分方案。

树链剖分的时间复杂度如下:

定义树上的一个树链剖分为一种将边集划分为重边和轻边的方法使得每个节点和他的儿子之间最多只有一条重边。

在下面的表示中,我们将重边称为0边,轻边称为1边。

定义树上的(x,y)序列为从xy依次经过的每一条边的类型拼接而成的一个01(x!=y)

对于一个长度为l的全1串,我们设f(x)=l

对于一个长度为l的全0串,我们设f(x)=log2l+1

对于一个01串,我们有f(x)=f(0/1)

例如:f(0011101)=(1+1)+3+(0+1)+1=7

对于一个轻重边划分方案T,我们有O(T)=i=2nf((1,i))

现在wangyisong1996想要知道所有可行的树链剖分方案中,时间复杂度(也就是O(方案))最小的值是多少

输入格式

第一行一个正整数n,表示有根树的节点数。

接下来n1行,每一行两个数字x,y,表示树上的一条连接x,y的边。

输出格式

一行一个数字,表示答案。

样例一

input

7
1 2
2 3
2 4
2 5
2 6
2 7

output

11

explanation

将边(1,2),(2,3)设为重边:

此时f(2)=1,f(3)=f(4)=f(5)=f(6)=f(7)=2,可以证明这是最优解。

样例二至样例四

见样例数据下载。

限制与约定

Subtask 1 (5 分): n20,内存限制1GB

Subtask 2 (15 分): n200,内存限制1GB

Subtask 3 (15 分): n5000,内存限制1GB

Subtask 4 (30 分): n100000,内存限制1GB

Subtask 5 (35 分): n100000,内存限制200MB

时间限制3s

下载

样例数据下载