《技术》学考及选考相关问题请联系张博士13958083702(手机和微信同号) 问题 5312 --树上求和(tree)

5312: 树上求和(tree)

时间限制: 1 Sec  内存限制: 512 MB
提交: 40  解决: 3
[提交][状态][命题人:]

题目描述

给一棵 n 个节点的树,第 i 个节点有一个颜色 c[i] 。

请问对于树上所有点对 (u,v) (1≤u<v≤n) ,它们路径上的点有多少种不同的颜色。输出所有点对的答案的和。

输入

第一行,一个整数 n ,表示节点个数。

接下来一行,一共 n 个整数 c[1],c[2],...,c[n] ,表示每个点的颜色。

接下来 n−1 行,每行两个数 u,v,表示树上的一条边。

输出

一行,一个整数,表示答案。

样例输入
Copy
6
1 2 1 3 2 1
1 2
1 3
2 4
2 5
3 6
样例输出
Copy
29

提示

数据规模
共 10 组数据。
测试点 1 满足 n≤100。
测试点 2,3 满足 n≤10^3。
测试点 4,5 满足 n≤2×10^5, 1≤c[i]≤20。
测试点 6,7 满足 n≤2×10^5,每种颜色节点数不超过 20 个。
对于 100%数据,满足 1≤n≤2×10^5, 1≤c[i]≤n。

来源

[提交][状态]

如有问题,请咨询客服
浙ICP备20001167号