GOCC18：2020年Google在线编码挑战赛-新毕业生（印度）

面向2021年新毕业生的Google 2020年在线挑战赛(GOCC++18)于2020年9月26日举行。

这是一个60分钟的在线测试, 需要解决2个编码问题。考试是在HackerEarth平台上进行的。

该过程是首先应将你的简历入围考试。

考试时间– 1小时

第一个问题：查询范围

你将得到一个包含N个整数的数组A。你需要回答以下类型的Q查询：

L R

确定将所有数组值从索引L划分为R的不同质数的计数。

注意：考虑基于1的索引

输入格式：

• 第一行包含一个整数T, 表示测试用例的数量。
• 每个测试用例的第一行包含一个整数N。
• 每个测试用例的第二行包含N个以A分隔的空格。
• 第三行包含整数Q。
• 接下来, Q行包含两个以空格分隔的整数, 表示查询。

输出格式;

打印将所有数组值从索引L划分为R的不同质数的计数。

经验：我已经使用段树解决了这个问题https://www.lsbin.org/segment-tree-set-1-range-minimum-query/请参阅有关范围最小查询的本文, 它与此问题类似。

第二个问题–加权树的价值

你将获得一个具有N个节点的加权无向树。每个边都有权重。

你需要找到∑(i = 1至N-1)∑(j = i + 1至N)F(i, j)函数的值, 其中F(i, j)表示边缘上权重的总和节点i和j之间的简单路径。

输入格式：

• 第一行包含一个整数T, 表示测试用例的数量。
• 每个测试用例的第一行包含一个整数N, 表示树中的节点数。
• 接下来的N-1行包含三个以空格分隔的整数u v w, 表示u和v之间权重为w的边。

输出格式：

对于每个测试用例, 在新行中打印函数模10 ^ 9 + 7的值。

---