UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3320. Seq

统计 下载数据

Description

给点一个N个点,N-1条边的无向连通图
每个点都有黑白的属性,如果树上一条路径上黑色点个数和白色点
个数一样多。称其为GOOD路径。易知两点间只有一条路径,那么给
定点A和点B就能确定一条路径了。
现给点集S,定义其GOOD值为以点集中的点两两确定的路径中GOOD路径
的个数。
现再给点一个序列,在一个方案中,某人可以选定其中一个连续子序列
作为他的点集,另一个人取走剩下的点。现某人想知道他的GOOD值比另一个人
的GOOD值大的方案数。

Input




第一个一个整数N,表示点的个数
接下来一行N个数,描述每个点的着色,黑色为1,白色为0
接下来N-1行,每行两个数a,b,表示一条连接a,b的边.
再接下来N个数,为1到N的排列,描述给定的序列。

Output


输出如题

Sample Input

1
0
1



Sample Output


0

Hint



N<=10^5

Source