You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

被 wmrqwq 吃掉了。

题目描述

给定一个 $n$ 个节点的树和 $n$ 个数字的序列 $a$，你需要求出 $\displaystyle \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} dis(i,j) \times [a_i = a_j]$ 的值，$dis(i,j)$ 是 $i$ 点到 $j$ 点的距离。

输入格式

第一行一个正整数 $n$。

之后 $n-1$ 行表示这个树的连接情况。

之后一行输入 $n$ 个数字的 $a$ 序列。

输出格式

一行一个正整数表示你的答案。

输入输出样例 #1

输入 #1

2
1 2
1 1

输出 #1

1

说明/提示

【数据范围】

对于 $20\%$ 的数据，$1 \le n \le 10$。

对于 $50\%$ 的数据，$1 \le n \le 4 \times 10^4$。

对于 $80\%$ 的数据，$1 \le n \le 6 \times 10^4$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 2 \times 10^5$。