注意到这个问题具有最优子结构性，考虑树上dp。记$dp[i][0/1]$表示i号节点不放灯或放灯的最小值，$s[i][0/1]$为对应的方案数。那么我们可以进行如下转移:$dp[u][0]=\sum_{u->v}dp[v][1]$$dp[u][1]=\sum_{u->v}\min(dp[v][0],dp[v][1])$在更新对应的dp数组时，我们用