记录编号 595205 评测结果 AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称 硝华流焰 最终得分 100
用户昵称 Gravatar┭┮﹏┭┮ 是否通过 通过
代码语言 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;
}