题解思路

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

P3431.第3题-小C的偶数

1000ms

Difficulty: 6

所属公司 : 饿了么

算法与标签>DFS

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

[名词解释]

第一行输入一个整数 $n(1≤n≦100000)$ ，代表树的节点数量.

接下来 $n-1$ 行,每行输入两个整数 $u_i$ 和 $v_i(1 ≦u_i,v_i≦n;u_i≠v_i)$ ,表示节点 $u_i$ 与节点 $v_i$ 之间有一条无向边。

输出 $n$ 行,第 $i$ 行输出一个整数，表示当以第 $i$ 个节点为根时，子树节点总数为偶数的节点个数。

输入

输出

说明

树结构是一条链 $1-2-3-4-5$ ;

当根为 $1$ 时,各节点子树大小为{ $5,4, 3, 2,1$ }，偶数子树大小的节点是 $2,4,$ 共 $2$ 个;

当根为 $2$ 时,各节点子树大小为{ $1,5,3,2,1$ }，偶数子树大小的节点是 $4，$ 共 $1$ 个;

当根为 $3$ 时，各节点子树大小为{ $1,2,5,2,1$ }，偶数子树大小的节点是 $2,4,$ 共 $2$ 个;

当根为 $4$ 时，各节点子树大小为{ $1,2,3,5,1$ }，偶数子树大小的节点是 $2,$ 共 $1$ 个;

当根为 $5$ 时,各节点子树大小为{ $1,2,3,4,5$ }，偶数子树大小的节点是 $2,4,$ 共 $2$ 个。

输入

输出

输入

预期输出（选填）