[POI2013] LUK-Triumphal arch

题目描述

The king of Byteotia, Byteasar, is returning to his country after a victorious battle.

In Byteotia, there are $n$ towns connected with only $(n-1)$ roads.

It is known that every town can be reached from every other town by a unique route, consisting of one or more (direct) roads.

(In other words, the road network forms a tree).

The king has just entered the capital.

Therein a triumphal arch, i.e., a gate a victorious king rides through, has been erected.

Byteasar, delighted by a warm welcome by his subjects, has planned a triumphal procession to visit all the towns of Byteotia, starting with the capital he is currently in.

The other towns are not ready to greet their king just yet - the constructions of the triumphal arches in those towns did not even begin!

But Byteasar's trusted advisor is seeing to the issue.

He desires to hire a number of construction crews.

Every crew can construct a single arch each day, in any town.

Unfortunately, no one knows the order in which the king will visit the towns.

The only thing that is clear is that every day the king will travel from the city he is currently in to a neighboring one.

The king may visit any town an arbitrary number of times (but as he is not vain, one arch in each town will suffice).

Byteasar's advisor has to pay each crew the same flat fee, regardless of how many arches this crew builds.

Thus, while he needs to ensure that every town has an arch when it is visited by the king, he wants to hire as few crews as possible.

Help him out by writing a program that will determine the minimum number of crews that allow a timely delivery of the arches.

输入格式

The first line of the standard input contains a single integer $n$ ($n \le 3 \times 10^5$), the number of towns in Byteotia.

The towns are numbered from 1 to $n$, where the number 1 corresponds to the capital.

The road network is described in $(n-1)$ lines that then follow.

Each of those lines contains two integers $(u,v)$ ($1\le u,v\le n$), separated by a single space, indicating that towns $u$ and $v$ are directly connected with a two way road.

In tests worth 50% of the total points, an additional condition holds.

输出格式

The first and only line of the standard output is to hold a single integer, the minimum number of crews that Byteasar's advisor needs to hire.

题意翻译

Byteotia 王国的国王 Byteasar，在一场胜利的战斗后，正在返回他的国家。

在 Byteotia 王国，有 $n$ 个城镇，它们之间只有 $(n-1)$ 条道路相连。

众所周知，每个城镇都可以通过一条独特的路线从其他任何城镇到达，这条路线由一条或多条（直接的）道路组成。

（换言之，道路网络形成了一棵树。）

国王刚刚进入了首都。

在那里，一座凯旋门，也就是一个胜利的国王骑马通过的门，已经建立起来了。

Byteasar 受到臣民热烈欢迎，计划举行凯旋游行，访问 Byteotia 的所有城镇，从他目前所在的首都开始。

其他城镇还没有准备好迎接他们的国王 - 那些城镇的凯旋门甚至还没有开始建造！

但是 Byteasar 的信任顾问正在处理这个问题。

他想雇佣一些建筑队。

每个队伍每天可以在任何城镇建造一座拱门。

不幸的是，没人知道国王会以什么顺序访问这些城镇。

每天国王都会从他所在的城市前往附近的一个城市，这是唯一清楚的事情。

国王可以任意多次访问任何城镇（但他不是虚荣的人，每个城镇有一座拱门即可）。

Byteasar 的顾问必须支付每个工作人员相同的固定费用，无论这些工作人员建造了多少座拱门。

因此，虽然他需要确保每个城镇在国王访问时都有一个拱门，但他希望雇用尽可能少的船员。

通过编写一个程序来帮助他，该程序将确定允许及时交付拱门的最小工作人员人数。

形式化地，给一颗 $n$ 个节点的树（$n \le 3 \times 10^5$），初始时 $1$ 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 $1$ 号节点。每一轮，A 选择至少 $k$ 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 $k$ 。

样例 #1

样例输入 #1

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

样例输出 #1

3