输入顺序为：

• $n,q,k$
• $(x_i,y_i,z_i)$
• $a_1,a_2\cdots a_k$
• $(p_i,q_i)$

含义如下：

给定一个 $n$ 个节点的树，给出一些三元组 $(x_i,y_i,z_i)$ 表示从子节点 $x_i$ 到父节点 $y_i$ 的边权为 $z_i$。

接着会给定 $k$ 个数 $a_1\sim a_k$。

接着会给定 $q$ 个询问，每个询问为 $p_i,q_i$。

对于每一组询问，求 $q_i$ 到 $p_i$ 最短路经过的所有边权（由于是树，所以最短路唯一），并记录下来；记录后，对于任意一个边权，出现的次数对 $2$ 取模。

如果这组边权中存在任意的一个 $x$，那就在纸上写下 $a_x$，最后求所有 $a_x$ 的乘积，结果对 $10^8+7$ 取模。如果纸上没有数，输出 $1$。

---

代码如下：

#include<bits/stdc++.h>
#define mod 100000007
#define int long long
using namespace std;
int n,q,k,a[25],l;
int fa[2][500005],path[25];
bool vis[500005];
void dfs1(int st){
	int next=st;
	while(fa[0][next]){
		next=fa[0][next];
		vis[next]=1;
	}
}int dfs2(int st){
	if(vis[st])return st;
	dfs2(fa[0][st]);
}void findpath(int st,int node){
	int ans=1,now=st;
	while(1){
		if(!now)break;
		int cur=fa[1][now];
		path[cur]=!path[cur];
		now=fa[0][now];
	}for(int i=1;i<=20;i++){
		ans=ans*a[path[i]]%mod;
	}cout<<max(ans,1)<<'\n';
}signed main(){
//	freopen("playgame.in","r",stdin);
//	freopen("playgame.out","w",stdout);
	cin>>n>>q>>k;
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		fa[0][x]=y;fa[1][x]=z;
	}for(int i=1;i<=k;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=q;i++){
		int x,y;
		scanf("%lld%lld",&x,&y);
		dfs1(x);int node=dfs2(y);
		findpath(x,node);
	}return 0;
}