封建王朝的等级制度非常森严，从皇帝开始，到各个部门的中央官员，再到地方官员。由于各个地方发展的不均衡，同一级别的官员可能拥有不同数量的手下（比如油水丰厚的县官就会有更多的人手），但是总体而言，官员体制可以表达为一颗有根树，每个节点代表一个官职。皇帝（编号为1）至高无上，手下的官员又继续管理下一级的节点，以此类推，形成了整个文官体系。

然而，即便是至高无上的皇权，历史上也经常遭受挑战。为了避免出现张居正的情况，皇帝可以通过将自己手下划分成两个不同的派系坐山观虎斗。两个派系的实力越接近，皇帝的位置就做的越稳。可是，由于事实上，皇帝只拥有罢免的人事权，所以皇帝也只能划分自己直接管理的手下（跟自己直接相连的子节点）的派系。譬如指定户部尚书为新派的人，于是所有隶属于户部的人（表现为子树的所有节点）都自动成为新派（但是户部真的会有尚书吗），指定兵部尚书为旧派的人，兵部的人同理成为旧派。一个派系的实力只取决于这个这个派系的人数。需要注意的是，没人能够不属于两派之一（这是常识）

当然，一个派系的内部同样有着子派系（极端和保守），子派系的内部还有着子子派系，以此类推。对于每一位官员而言，即使他的手下只有一个人，他都要划分出两个内部派系，使两个派系的人数相近而自己坐山观虎斗。而每一个官员也只能划分自己直接相连的人的（子）派系。

当然，作为一个历史学者，你并不关心具体谁是哪个派系的，但是你关心即使每个官员（包括皇帝）都做出最优的选择的情况下，每个节点需要面对的派系的实力差是多少。派系的实力差指两个派系的人数差。

需要特别注意的是，本题会适度的卡常，但是正确算法的理论复杂度是没有问题的。

第一行一个整数表示节点数量，第二行开始的行每行两个数字表示两个节点之间有边

输出一个数组，代表每个节点的最优选择下的派系人数差

6
1 2 
2 3
2 4
1 5
1 6

1 0 0 0 0 0

解释：输入是一颗树。
对于节点1，将节点2划分成旧派（人数3），5、6划分成新派（人数1+1=2）。
对于节点2，将节点3划分成旧派，4划分为新派
其他节点都是打工的叶子节点。

节点数量，轻微卡常
需要注意的是，本题有多种解法，其中一种解法可以通过bitset优化。