题解思路

问题抽象

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

题目内容

给定一棵包含$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

输入

5
1 2
2 3
3 4
4 5

输出

2
1
2
1
2

说明

树结构是一条链$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$个。

样例2

输入

7
1 2
1 3
2 4
2 5
3 6
3 7

输出

0
1
1
2
2
2
2