比赛 2024暑假C班集训B 评测结果 AWWWWWWWWW
题目名称 Asm.Def的基本算法 最终得分 10
用户昵称 djyqjy 运行时间 0.104 s
代码语言 C++ 内存使用 4.23 MiB
提交时间 2024-07-11 11:42:16
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
const long long MOD=1000000007;
long long ww[N],w[N];
int p[N];
int ver[2*N],nxt[2*N],hd[N];
int jsq=1;
int n;
long long ans;
void add(int x,int y)
{
	ver[++jsq]=y;
	nxt[jsq]=hd[x];
	hd[x]=jsq;
	return;
}
long long dfs(int x)
{
	long long sum=0,sumw=0;
	for(int i=hd[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y==p[x]) continue;
		ww[x]=(ww[x]+dfs(y))%MOD;
		sum=(sum+(ww[y]*ww[y])%MOD)%MOD;
		sumw=(sumw+ww[y])%MOD;
	}
	ans=(ans+(((sumw*sumw-sum)%MOD*2)%MOD*w[x])%MOD)%MOD;
	ans=(ans+(w[x]*w[x]%MOD*(sumw*2+w[x])%MOD)%MOD)%MOD;
	return ww[x];
}
int main()
{
	freopen("asm_algo.in","r",stdin);
	freopen("asm_algo.out","w",stdout);
	scanf("%d%lld",&n,&ww[1]);
	w[1]=ww[1];
	for(int i=2;i<=n;i++)
	{
		scanf("%d%lld",&p[i],&ww[i]);
		w[i]=ww[i];
		add(i,p[i]);
		add(p[i],i);
	}
	dfs(1);
	printf("%lld",(ans%MOD+MOD)%MOD);
	return 0;
}