题目描述

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

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

题面描述

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

思路：树形DP

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

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