1000ms

Difficulty: 6

所属公司 : 饿了么

时间 :2025年8月22日(算法方向)

算法与标签>DFS

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

题解思路

问题抽象

固定一棵无向树，总节点数为 $n$ 。若以节点 $r$ 为根，则每个节点 $u$ 都对应一棵子树，大小记为 $\text{sz}_r(u)$ 。题目要求：对每个根 $r$ ，统计满足

题目内容

给定一棵包含 $n$ 个节点的无向树。小 $C$ 特别喜欢偶数，他想知道:当以第 $i$ 个节点作为根节点时，有多少个节点的子树节点总数是偶数？请你计算并输出所有 $i$ 的答案。

[名词解释]

树:树是一个连通且无环的无向图，由若干节点和边构成。
子树:子树是以某个节点为根，该节点及其所有后代节点构成的连通子图。