题目描述

给定一颗n个点的每个点都有权值的树，问树中每个子树的点权和，点权最大值。

$n \leq 10^5$

输入格式

第一行输入一个正整数n（2≤n≤10^5）;

第二行输入n个正整数d(1≤d≤2700000000),表示每点的权值。

第三行到第n+1行输入每条边的信息，每行输入两个整数u（1≤u≤n）,v（1≤v≤n）。分别表示边的两个结点。

数据保证输入的是一棵树。

输出格式

共两行;

第一行输出n个数,表示当前点所包含最大子树的点权和;

第二行输出n个数,表示当前点所包含最大子树的最大点权;

不过滤行末空格

样例数据

input

5

1 3 6 8 7

1 2

1 3

3 4

2 5

output

25 10 14 8 7

8 7 8 8 7

数据规模与约定

数据范围规定

第1、2组数据：n<=10；

第3组数据：100<=n<=50；

第4组数据：500<=n<=1000；

第5组数据：1000<=n<=5000；

第6组数据：n=75000；

第7组数据：10000<=n<=50000；

第8组数据：50000<=n<=100000；

第9、10组数据：n=100000；

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$