红黑树

题目背景

你学过红黑树吗？

题目描述

你有一颗 $n$ 个点的无根树，每个点都有红黑之一的颜色，初始时每个点都是红色的。

你可以多次操作这棵树。每次操作是选择一个红色点，把它变成黑色。如果这个点第一次被操作，和它相邻的所有点都会变成红色。

求把所有点都变成黑色的最小操作次数。

输入格式

第一行一个整数 $n$，表示树有 $n$ 个点。点从 $0$ 到 $n-1$ 编号。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示有一条连接编号为 $u,v$ 的点的无向边。

输出格式

输出一个整数表示最小操作次数。

样例 #1

样例输入 #1

3
0 1
1 2

样例输出 #1

4

提示

对于 $25\%$ 的数据，树是一条链。
对于另外 $25\%$ 的数据，树是菊花。
对于另外 $25\%$ 的数据，$n\le 20$。
对于全部数据，$2\le n\le 100000$，$0\le u,v\le n-1$。保证输入的是一棵树。

Solution

图论、贪心、动态规划、树形动态规划

分析可知一个节点至多被染色两次，考虑最大化被染色一次的节点数量。令题目给出的点集为 $V$，边集为 $E$，找到 $V$ 的一个满足 $\forall\ u,v \in S,(u,v) \notin E $ 的子集 $S$，使得 $|S|$ 最大。对 $\complement_V S$ 进行染色后对 $S$ 染色，此时 $\complement_V S$ 被染回红色。最后将 $\complement_V S$ 染色，由于被染色过一次，这些节点的邻点不会被染回红色。

发现 $S$ 为树上最大独立集，树形 dp 求出其大小后可计算答案。