2312: 魔法树
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：16
解决：7
题目描述
作为回报，小 Y 的朋友小 Z，送给小 Y 一棵魔法树，据说这棵魔法树上隐藏
了神秘宝藏的藏宝图。
魔法树顾名思义，是一棵树，奇葩的是魔法树上的每一条边都拥有一个魔法
属性，每一个魔法属性对应着一个魔法系数。
破解魔法树的唯一方法就是找一条树上的路径，使得这条路径所能获得的魔
法值最大。
一条路径上的魔法值是这样计算的：在起点的时候，魔法值为 1，每经过一
条边，假设这条边拥有的魔法属性是 ci，那么如果这是奇数次经过带有 ci 魔法
属性的边，则将魔法值乘上 ci 对应的魔法系数，否则将魔法值除以 ci 对应的魔
法系数。
为了帮助小 Y 找到藏宝图，对于每条选定的路径，你需要告诉小 Y 能获得的
魔法值对 100000007 取 mod 后的值是多少？
输入
输入第一行包含两个整数 N,Q,K,表示魔法树的大小，询问数以及魔法属性的
数量。
接下来 N-1 行，每行表示一条魔法树上的边 ai,bi,ci，表示一条连接 ai,bi
两个点的边带有魔法属性 ci。
接下来一行，K 个整数，表示每种魔法属性对应的魔法系数 di。
接下来 Q 行，每行一组询问，pi,qi 表示选定路径的起点和终点。
每一行的若干个数之间都有且仅有一个空格分开。
输出
对于每组数据输出一行一个数，表示该组询问的答案。
样例输入 复制
5 4 3
1 2 2
1 5 3
2 3 2
2 4 1
1 2 3
3 5
1 3
4 5
4 4样例输出 复制
3
1
6
1提示
【数据规模】
对于 40%的数据，N,Q≤1000；
对于 80%的数据，N≤100000，Q≤40000；
对于 100%的数据，N,Q≤500000，1≤ci≤K≤20，1≤ai,bi,pi,qi≤N，
di≤100000000；
对于所有奇数点的数据满足所有 pi=1。