弱对

成绩 100 开启时间 2020年06月18日 星期四 11:05
折扣 0.8 折扣时间 2020年06月18日 星期四 11:05
允许迟交 是 关闭时间 2020年06月18日 星期四 11:05
输入文件 weak.in 输出文件 weak.out

【题目描述】弱对（weak）HDU 5877

有n个结点的一棵树，结点编号为1~n，每个结点a[i]有一个非负整数，现求弱对（u，v）的个数，满足：

（1）u是v的祖先结点。

（2）a[u]×a[v]≤k。

【输入格式】

第一行一个整数T表示有T组数据。

每组数据第一行有两个整数n（1≤n≤105）和k(0≤k≤1018)。第二行为n个整数，表示树的结点权值a[i](0≤ai≤109 )。

随后每一行有两个整数u和v，表示结点u是结点v的祖先结点。

【输出格式】

输出弱对的个数。

【输入样例】

1

2 3

1 2

1 2

【输出样例】

1