时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小H收到了一棵美丽的圣诞树，圣诞树是一棵树(废话)，有N个节点，编号为1~N，每个节点上都有一件礼物，礼物也分为N种，编号为1~N，每件礼物都有一个种类。
现在小H想问你Q个问题，每个问题形如x，y，表示询问所有满足下列条件的路径长度和：
路径的一个端点上的礼物种类是x，另一端点上礼物种类是y，且这条路径是简单路径
注意：
(x,y),(y,x)是相同的路径
树的每条边有边权，路径的长度为路径上所有边的长度和
输入描述:
第1行，一个整数N(1≤N≤100,000)
第2行N个属于[1,N]的正整数，依次表示每个节点上的礼物种类
接下来N-1行，每行三个正整数，依次表示树上的一条边的起点u、终点v、长度l (1≤u,v≤N,0≤l≤100,000)
接下来一行，一个整数Q(1≤Q≤100,000)
接下来Q行，每行两个整数x，y，意义见题目描述,1≤x,y≤N
输出描述:
对于每个询问输出一行，表示你给出的答案(答案保证在long long范围内)
示例1
输入
复制
3
1 2 3
1 2 3
2 3 7
3
1 2
1 3
2 3