题面描述

塔子哥组织了一场小朋友的游戏，需要分发糖果以确保每根绳子的两端至少有一个小朋友开心。每个小朋友可以牵引多个同学，形成树形结构。通过合理分配糖果，目标是用最少的糖果让每个小朋友开心，从而实现快乐的游戏氛围。输入包含小朋友数量及其牵引关系，输出所需的最少糖果数。

思路：树形DP

定义$f[i][j]$为以$i$为结点的子树中，不放消防栓/放消防栓（$j=0/1$）的最小个数

如果在第$i$个结点放置消防栓，那么对于结点$i$的所有子节点，都可以放置/不放置消防栓

题目描述

小明组织小朋友们在玩一场小游戏, 一共有$n$个小朋友, 编号为$0 ... n-1$, 每个小朋友身后都有一根绳子, 一个小朋友可以不拿或者拿多个同学的绳子, 拿完之后小明会让小朋友们保持不动, 给小朋友发糖果。

给一个小朋友分糖果, 他就会开心, 否则他就会不开心。

可是小明的糖果没有很多了, 怎么分才能使最少的糖果让每个绳子两头都最少有一个开心的小朋友呢

(一个小朋友只能被一个小朋友牵, 一个小朋友可以牵多个小朋友, 最终类似一个树形结构, 题目保证所有小孩子都牵了人或者被人牵)

输入描述

第一行一个整数$n$，表示小朋友数量$(1\le n\le 1500)$ 接下来$n$行，每行以$a:(b)$ 这样的格式开头，$a$表示小朋友的编号$(0\le a\le n-1)$ $b$表示第$i$个小朋友牵了几个小朋友,接下来$b$个数，表示被牵的小朋友的编号

输出描述

一个数字，为需要的糖果的最少个数

样例

输入1

3
0:(2) 1 2
1:(0)
2:(0)

输出1

1

说明

0号小朋友与1号和2号相连，那么只需要给0号发一个糖果就可使得所有绳子两端都有开心的小朋友

输入2

8
0:(3) 1 2 3
1:(1) 6
2:(0)
3:(0)
6:(1) 7
7:(2) 4 5
4:(0)
5:(0)

输出2

3

说明 给 0, 6, 7号小朋友发糖果, 就可使得所有绳子两端都有开心的小朋友