据守要隘

圆码遴选完了，但Zero的防御节点还在——废墟里有据点和通道，像一张网。

"要守。"CC说，"每条通道至少一端有哨兵。"

"最少要几个哨兵？"

"树形DP。"你说，"把据点看成树，选最少的节点，覆盖所有边。"

"覆盖？"

"对。"你说，"每条边连接两个据点。如果其中一个有哨兵，这条通道就被守住了。"

"那选叶子？"

"不一定。"你说，"选叶子可以守住一条边，但可能不是最优。"

"咋算？"

"$dp[u][0]$：$u$不放哨兵时，子树最少哨兵数。"你说，"$dp[u][1]$：$u$放哨兵时，子树最少哨兵数。"

"$u$不放哨兵——它的所有儿子必须放。"

"对。"你说，"$dp[u][0]=\sum dp[v][1]$。"

"$u$放哨兵——儿子可放可不放，取min。"

"对。"你说，"$dp[u][1]=1+\sum\min(dp[v][0],dp[v][1])$。"

你开始写。DFS遍历树，自底向上DP。

"根节点。"你说，"如果根放哨兵，$dp[root][1]=1+\sum\min(dp[v][0],dp[v][1])$。"

"如果根不放——"

"根不能不放。"你说，"根没有父亲，如果它不放，没人守它连出去的边。"

"所以根必须放？"

"不一定。"你说，"如果根只有一个儿子，且儿子放哨兵，根连出去的边也被守了。"

"但根不是叶子吗？"

"根没有父节点，但有子节点。"你说，"根不放哨兵，它的所有子节点必须放。"

"所以答案=$\min(dp[root][0], dp[root][1])$。"

"对。"

CC扛着数据刀，站在一个据点门口——那是通往Zero核心最后的关卡。

"我守这。"她说。

"你一个人？"

"我够。"她说，"这条通道，我守住了。"

"但还有其他通道——"

"你们去守别的。"她说，"分散开。每条通道至少一端有人。"

Echo的投影分成了许多份——每份守一个节点。

"我也守。"她说，"我的投影可以同时在多个点。"

"那你累吗？"

"累。"她说，"但值得。"

你看着那些发光的节点——有些亮了（有哨兵），有些暗了（没有）。亮着的连成一片，像一张网，把Zero困在里面。

"网织好了。"你说，"下一步。"

"下一步？"CC问。

"丈量扰动。"你说，"算我们走不同路的代价。"

题目描述

给定一棵树，选最少数量的节点，使得每条边至少有一个端点被选。

输入格式

$n$。然后$n-1$条边。

输出格式

最少节点数。

输入样例

3
1 2 3

输出样例

0

提示

• 树形DP。
• $dp[u][0]$：$u$不选时子树最少节点数。
• $dp[u][1]$：$u$选时子树最少节点数。
• $dp[u][0]=\sum dp[v][1]$。
• $dp[u][1]=1+\sum\min(dp[v][0],dp[v][1])$。