记录编号 |
595205 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
题目名称 |
硝华流焰 |
最终得分 |
100 |
用户昵称 |
┭┮﹏┭┮ |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
2.297 s |
提交时间 |
2024-10-10 19:42:32 |
内存使用 |
23.30 MiB |
显示代码纯文本
#include<bits/stdc++.h>
#define maxn 100010
#define ll long long
using namespace std;
const ll mod=(ll)(1e9+7);
int n,a[maxn],a1,a2;
ll a3,f[maxn][8],g[maxn][9],ans;
vector<int>b[maxn];
vector<ll>c[maxn];
void solve(int p,int fa){
int fz=(1<<a[p]);
g[p][fz]=1;
for(int i=0;i<b[p].size();i++){
if(fa==b[p][i])continue;
solve(b[p][i],p);
for(int j=0;j<8;j++)
for(int k=0;k<8;k++)
if((j|k)==7)
ans=(ans+f[p][j]*g[b[p][i]][k]%mod+(f[b[p][i]][k]*g[p][j])%mod+(c[p][i]*g[p][j]%mod*g[b[p][i]][k])%mod)%mod;
for(int j=0;j<8;j++){
f[p][j|fz]=(f[p][j|fz]+f[b[p][i]][j]+c[p][i]*g[b[p][i]][j])%mod;
g[p][j|fz]=(g[p][j|fz]+g[b[p][i]][j])%mod;
}
}
return;
}
int HS(){
freopen("blossom.in","r",stdin);
freopen("blossom.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++){
scanf("%d%d%lld",&a1,&a2,&a3);
b[a1].push_back(a2);c[a1].push_back(a3);
b[a2].push_back(a1);c[a2].push_back(a3);
}
solve(1,0);
printf("%lld\n",ans);
return 0;
}
int sb=HS();
int main(){
return 0;
}