欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1247. -- Glory and heuristic method

1247: Glory and heuristic method

时间限制: 2 Sec  内存限制: 128 MB
提交: 7  解决: 3
[提交][状态][讨论版]

题目描述

一天,williamchenwl88在给他优秀的徒弟Glory讲解LCA(最近公共祖先)。因为Glory太优秀了所以一下就学会了,谁知williamchenwl88却说“你还是太菜了”,然后丢给了Glory一道题。虽然对Glory来说这是一道非常简单的题,但是比起向williamchenwl88证明自己不菜还是把妹更重要,于是忙着把妹的Glory就把这道题丢给了没有妹子的你。

给你一棵有根树,根节点的编号为1,每个节点有一个权值A[i],问有多少无序点对(u, v)满足u != v且A[u]*A[v]=A[lca(u, v)]

输入

第一行一个数字T表示数据组数。

每组数据的第一行是一个整数n(n<=30000)表示节点个数。

接下来n-1行,每行两个数字u,v表示树上有一条边(u, v)

接下来一行n个数字表示A[1] ……A[n]。(A[i]<=10^9)

输出

每组数据输出一个数字表示答案。

样例输入

1
6
1 2
1 3
2 4
2 5
5 6
6 2 3 1 8 2

样例输出

5

提示

来源

[提交][状态][讨论版]