Callisto滑滑板

在一个魔法公园里面有$n$个小卖部，这$n$个小卖部由$n-1$条路径连接并相互可以抵达。我们都知道杭州是丘陵地形，地面起起伏伏，每个小卖部的高度都有不一样。一些小卖部的高度为$0$，还有一些小卖部的高度不为零。因为这个公园曾经被Eruopa施展过魔法，小卖部之间的路径长度都为$1$，同时小卖部的地形高度是这个小卖部与最近的高度为$0$的小卖部的最短路径的长度。

Callisto来到这个公园里面玩滑板，他和妈妈约定每到一个小卖部妈妈就要给Callisto买一个雪糕，Callisto可开心了。他想经过这个公园所有的小卖部，这样他就可以获得无穷无尽的雪糕了。但是他发现一个问题，他因为不会上坡无法前往比当前自己所在小卖部地势高的小卖部。如果他要前往和自己当前地势一样高的小卖部速度会$-1$，前往比自己当前地势低的小卖部速度会$+1$，行进途中不允许速度小于$0$。Callisto开始时候的速度为$0$。Callisto想知道他最多可以吃到多少个雪糕，请输出他从每个小卖部出发的答案。（为了激励Callisto，妈妈开始之前就会在起点的小卖部给Callisto买一个雪糕。）

允许Callisto前往同一个小卖部多次或者经过同一条路径多次。

第一行包含一个整数$n(1 \le n\le 2*10^5)$。

第二行包含$n$个整数$l_i(l_i\in \{0,1\}, 1 \le i \le n)$，$l_i=1$表示第$i$个小卖部高度为$0$，$l_i=0$表示第$i$个小卖部高度不为$0$。确保至少存在一个高度为0的小卖部。

接下来$n-1$行，每行两个整数$x,y(1 \le x, y \le n, x \neq y)$表示小卖部$x$和小卖部$y$之间有一条路径。确保这些路径形成一棵树。

共一行，包含$n$个数，第$i$个数$(1 \le i \le n)$表示从第$i$个小卖部开始，在速度不为负的情况下能够经过最多的小卖部数量。

6
1 1 0 0 0 0
1 3
2 4
3 4
4 5
5 6

1 1 2 2 4 6

样例如上图所示，h=[0, 0,1,1,2,3]. Callisto从6号小卖部出发经过最多小卖部的路径为6→5→4→3→4→2(Callisto可以经过同一个小卖部和同一路径多次):

• 在6号小卖部, 当前速度为0;
• 到5号小卖部, 速度增加了1 (由于$h_5 \lt h_6$) , 所以当前速度为1;
• 到4号小卖部, 速度增加了1 (由于$h_4 \lt h_5$), 所以当前速度为2;
• 到3号小卖部, 速度减少了1 (由于$h_3 = h_4$), 所以当前速度为1;
• 到4号小卖部, 速度减少了1 (由于$h_4 = h_3$), 所以当前速度为0;
• 到2号小卖部, 速度增加了1 (由于$h_2 \lt h_4$), 所以当前速度为1。

在速度不为负的情况下，已经没有其他行走路线比这个更长了。由于出发时就吃到一个雪糕，所以最终吃到6个雪糕。

此外,

• 从1号小卖部出发的最优路径是1(没有路径);
• 从2号小卖部出发的最优路径是2(没有路径);
• 从3号小卖部出发的最优路径是3→1;
• 从4号小卖部出发的最优路径是4→2;
• 从5号小卖部出发的最优路径是 5→4→3→1。