题目描述

一座树形迷宫里有 $n$ 个储物点，编号为 $1$ 到 $n$。相邻储物点之间由通道连接，并且任意两个储物点之间只有一条简单路径。

管理员给出了一条巡检路线 $a_1,a_2,\ldots,a_n$。巡检员从 $a_1$ 出发，依次前往 $a_2,a_3,\ldots,a_n$。每次从当前点移动到下一个目标点时，他都会沿树上的唯一简单路径行走。

巡检员每次到达一个储物点时，都需要消耗该点的一枚标记牌。若连续两段路线在同一个目标点衔接，这个衔接点只按到达一次计算。

请你计算，为了完成整条巡检路线，每个储物点至少要预先放多少枚标记牌。

输入格式

第一行输入整数 $n$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示巡检员依次到达的储物点编号。

接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示两个储物点之间有一条通道。

输出格式

输出 $n$ 行，第 $i$ 行表示编号为 $i$ 的储物点需要准备的标记牌数量。

样例

4
1 3 4 2
1 2
2 3
2 4

1
2
1
1

样例说明

巡检路线为 $1\to3\to4\to2$。

把每段路线经过的点都统计一次后，再去掉每段终点处与下一段起点重合的重复到达。

三段路径分别为 $1\to2\to3$、$3\to2\to4$、$4\to2$。其中 $3$ 是第一段终点和第二段起点的重合点，$4$ 是第二段终点和第三段起点的重合点，最后的终点 $2$ 不需要再为下一次出发准备标记牌。

因此 $1,2,3,4$ 号点分别需要 $1,2,1,1$ 枚标记牌。

数据范围

• 对于 $50\%$ 的数据，$n\le 100$。
• 对于 $100\%$ 的数据，$2\le n\le 300000$，$1\le a_i,u,v\le n$，输入的边构成一棵树。