题目描述

给定一颗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；