记录编号	599844	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	硝华流焰	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	1.448 s
提交时间	2025-03-29 15:50:30	内存使用	16.92 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=100010,MOD=1e9+7;
struct edge
{
    int ver[2*N],edge[2*N],nxt[2*N],hd[N];
    int jsq=1;
    inline void add_edge(int x,int y,int z)
    {
        ver[++jsq]=y;
        edge[jsq]=z;
        nxt[jsq]=hd[x];
        hd[x]=jsq;
        ver[++jsq]=x;
        edge[jsq]=z;
        nxt[jsq]=hd[y];
        hd[y]=jsq;
        return;
    }
}g;
int n,ans;
int a[N],dp[N][8],dp2[N][8];//dp:路径权值和 dp2:路径条数
void dfs(int x,int fa)
{
    dp2[x][1<<a[x]]=1;
    for(int i=g.hd[x];i;i=g.nxt[i])
    {
        int y=g.ver[i];
        if(y==fa) continue;
        dfs(y,x);
        for(int c1=0;c1<8;c1++) for(int c2=0;c2<8;c2++) if((c1|c2)==7)
            ans=(ans+dp[x][c1]*dp2[y][c2]%MOD+
                dp2[x][c1]*dp[y][c2]%MOD+
                dp2[x][c1]*dp2[y][c2]%MOD*g.edge[i]%MOD)%MOD;
        for(int c=0;c<8;c++)
        {
            dp[x][c|(1<<a[x])]=(dp[x][c|(1<<a[x])]+dp[y][c]+dp2[y][c]*g.edge[i]%MOD)%MOD;
            dp2[x][c|(1<<a[x])]=(dp2[x][c|(1<<a[x])]+dp2[y][c])%MOD;
        }
    }
    return;
}
signed main()
{
    freopen("blossom.in","r",stdin);
    freopen("blossom.out","w",stdout);
    n=re();
    for(int i=1;i<=n;i++) a[i]=re();
    for(int i=1,x,y,z;i<n;i++) x=re(),y=re(),z=re(),g.add_edge(x,y,z);
    dfs(1,0);
    printf("%lld",ans);
    return 0;
}