题目描述

给定一棵包含n个节点的无向树，节点编号从1到n。每个节点都有一个正整数权值。请你从1号节点开始进行深度优先搜索（DFS），并计算以下两个值：

1. 路径和：从根节点（1号节点）到当前节点的路径上所有节点的权值之和
2. 子树和：以当前节点为根的子树中所有节点的权值之和

要求输出每个节点在首次被访问时的路径和，以及在回溯离开时的子树和。每个节点的两个值用空格分隔，节点之间按DFS首次访问顺序排列。

输入描述

第一行输入一个整数n，表示树的节点总数。 第二行输入n个正整数，分别表示1到n号节点的权值。 接下来n-1行，每行输入两个整数x和y，表示树中存在一条连接x和y的边。

输出n行，每行两个整数，分别表示对应节点的路径和与子树和。节点顺序按DFS首次访问顺序排列。

输入样例

3
2 3 4
1 2
1 3

输出样例

2 9
5 3
6 4

数据范围

1≤n≤100000，节点权值1≤w≤1000。