AtCoder Regular Contest 148 C Lights Out on Tree

挺好的一道题，简单写一下题解吧。
首先有挺多很 naive 的结论：

• 每个节点按两遍等于没按。
• 熄灭所有的灯只有一种方案。

其实将灯熄灭的方案无非就是从上往下 dfs，如果当前灯是量的，就在当前节点按一下，否则不按。这样我们就可以写出暴力了。

考虑一下，如果树上只有一个节点 \(u\) 开始亮灯，那么需要按的灯即为 \(u\) 和所有 \(u\) 的儿子，设这个集合为 \(\{v\}\)。

进一步考虑一下，若初始的亮灯集合为 \(\{u_1,u_2,u_m\}\)，那么所有需要按的集合即为 \(\{v_1,v_2,v_m\}\)，再根据上面的第一个结论：每个节点按两遍等于没按，所以只需要求出在 \(\{v_1,v_2,v_m\}\) 集合中出现次数为奇数的节点个数。