题目描述

有一棵包含 $n$ 个点的树，点的编号为 $1,2,\ldots,n$。另给出一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$。

对于排列中的一个非空连续片段 $p_l,p_{l+1},\ldots,p_r$，取出这些点以及原树中两端都在这些点内的边，得到这个点集在原树上的诱导子图。

如果该诱导子图连通，且其中每个点的度数都不超过 $2$，那么它是一条简单路径，称这个连续片段为合法片段。特别地，只包含一个点的片段也合法。

求合法片段的数量。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树中有一条连接点 $u$ 与点 $v$ 的边。

最后一行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示给定的排列。

输出格式

输出一个整数，表示合法片段的数量。

数据范围

对于所有测试数据：

• $1\le n\le 2\times 10^5$；
• 输入的 $n-1$ 条边构成一棵树；
• $p$ 是 $1$ 到 $n$ 的一个排列。

子任务

样例 1

5
1 2
1 3
1 4
4 5
2 1 3 4 5

11

样例 1 说明

长度为 $1$ 的 $5$ 个片段都合法；长度为 $2$、$3$、$4$ 的合法片段分别有 $3$、$2$、$1$ 个。完整片段中点 $1$ 的诱导度数为 $3$，因此不合法。总数为 $5+3+2+1=11$。