- #include <cstdio>
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #define ll int
- using namespace std;
- const ll mod=100000007;
- inline void read(ll &k)
- {
- ll f=1;char c=getchar();k=0;
- while (c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
- while (c>=‘0‘&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
- k*=f;
- }
- const int maxn=1000010;
- ll n,q,k,aa,bb,cc;
- ll last[maxn],next[maxn],tot,c[maxn],to[maxn],sum[maxn];long long cost[233];
- bool v[maxn];
- void dfs(ll now,ll fa)
- {
- v[now]=1;ll cur=last[now];
- while (cur)
- {
- if (!v[to[cur]])
- {
- sum[to[cur]]=sum[now]^(1<<(c[cur]-1));
- dfs(to[cur],now);
- }
- cur=next[cur];
- }
- }
- int main()
- {
- freopen("mahou.in","r",stdin);
- freopen("mahou.out","w",stdout);
- read(n);read(q);read(k);
- // printf("..............qaq%lld%lld%lld\n",n,q,k);
- for (int i=1;i<n;i++)
- {
- read(aa);read(bb);read(cc);
- to[++tot]=bb;
- next[tot]=last[aa];
- last[aa]=tot;
- c[tot]=cc;
- to[++tot]=aa;
- next[tot]=last[bb];
- last[bb]=tot;
- c[tot]=cc;
- }
- dfs(1,0);
- for (int i=1;i<=k;i++)scanf("%lld",&cost[i]);
- ll pp,qq;
- for (int i=1;i<=q;i++)
- {
- long long ans=1;
- read(pp);read(qq);
- ll cur=sum[pp]^sum[qq];
- for (int j=1;j<=k;j++)
- if (cur&(1<<(j-1)))ans=(long long)((long long)ans*cost[j])%mod;
- printf("%lld\n",ans%mod);
- }/*
- for (int i=1;i<=n;i++){printf("%d ",i);
- for (int j=1;j<=k;j++)
- printf("%lld ",sum[i][j]);
- printf("\n");
- }*/
- }
来源: http://www.bubuko.com/infodetail-2303197.html