题目描述

给你一棵 $n$ 个节点的二叉树，节点的编号为 1 到 $n$，二叉树的根为 1 号节点。每个节点都有一个权值，$i$ 号节点的权值为 $a_i$，请求出每个节点的子树的权值和 （子树内节点的权值的和）。

输入格式

第一行一个整数 $n$ 表示节点数。

接下来 $n$ 行，每行两个整数，第一个整数表示 $i$ 号节点的左儿子的编号，第二个整数表示 $i$ 号节点的右儿子的编号，如果某个数字为 0 表示没有对应的子节点。

输入保证是一棵二叉树。

接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示 $i$ 号节点的权值。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示 $i$ 号节点的子树的权值和。

4
2 3
0 0
4 0
0 0
1 1 1 1

4 1 2 1

数据规模

对于所有数据，保证 $1≤n≤1000,1≤a_i≤100$。