问题 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,表示树上的一条边。
输出
提示
数据规模
共 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。
来源
[提交][状态]