UOJ Logo

NOI.AC

1S 512MB
Statistics

题目描述

给定一颗 $n$ 个节点的有根树,规定节点 $1$ 为该树的根。

定义 $l=(c_1,c_2,\cdots,c_m)$ 是树上的一条合法路径,当且仅当其满足:

  1. 对于 $\forall 1\le i\lt m$,树上存在一条边 $(c_i,c_{i+1})$;
  2. $c_1=1$。

记该路径的权值 $v_l$ 为其总长度 $m-1$。

构造一个路径集 $S=\left\{l_1,\cdots,l_k\right\}$,使得对于树上任意点 $1\le x\le n$,至少存在一个 $l_j\in S$ 满足 $x$ 存在于其路径上。记此路径集的权值 $V_S$ 为其包含的所有路径的权值之和,即 $V_S=v_{l_1}+\cdots+v_{l_k}$。

最小化 $V_S$,并输出这个值。

输入格式

第一行一个整数 $n$。

后面 $n-1$ 行,每行两个数 $x,y$,表示一条树上的边 $(x,y)$。

输出格式

一行共一个整数,表示满足要求的最小的 $V_S$。

样例输入 #1

6
1 2
2 3
1 4
2 5
5 6

样例输出 #1

6

样例解释 #1

该树可以构造出满足要求的路径集 $S=\left\{(1,4),(1,2,3,2,5,6)\right\}$,其权值为 $6$。

值得注意的是,另一个满足要求的路径集 $S_2=\left\{(1,4),(1,2,3),(1,2,5,6)\right\}$ 权值亦为 $6$。

容易证明不存在一个合题路径集使得其权值小于 $6$。

样例输入 #2

5
1 2
2 3
3 4
4 5

样例输出 #2

4

数据规模与约定

注意,按照题目的定义,路径经过的点是可重的。

本题目采用 $\text{subtask}$ 测试

对于 $100\%$ 的数据,$1\le n\le 10^6$,$1\le x,y\le n$。

具体数据范围如下:

$\text{subtask 1(10pts)}$:$1\le n\le 5$;

$\text{subtask 2(20pts)}$:$1\le n\le 100$;

$\text{subtask 3(20pts)}$:$1\le n\le 1000$;

$\text{subtask 4(20pts)}$:$1\le n\le 10^5$;

$\text{subtask 5(30pts)}$:无特殊限制。