CSP-J 二叉树专题原创训练。

题目描述

有 n 个区域组成一棵以 1 为根的二叉树。第 i 个区域有 ai 个果实，并给出其左孩子 Li 与右孩子 Ri，不存在的孩子编号为 0。

对于每个节点 i，请求出：

1. 以 i 为根的子树节点数量；
2. 以 i 为根的子树果实总数。

输入格式

第一行 n。 第二行 n 个整数 a1...an。 接下来 n 行，第 i 行两个整数 Li Ri。

输出格式

输出 n 行，第 i 行输出 cnt sum。

样例

输入：

7
5 3 8 2 4 6 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0

输出：

7 35
3 9
3 21
1 2
1 4
1 6
1 7

数据范围

1 <= n <= 200000，1 <= ai <= 10^9。 保证输入是一棵以 1 为根的二叉树。