记录编号	587703	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的基本算法	最终得分	100
用户昵称	Untitled	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2024-04-18 20:26:24	内存使用	2.06 MiB

#include <bits/stdc++.h>
#define ll long long
using namespace std;
//typedef long long ll;

ll const N=100010,mod=1e9+7;
ll n,idx;
ll res,w[N],siz[N];
ll head[N],Next[N],ver[N],fat[N];

ll mul(ll a,ll b){
	return (a*b)%mod;
}

void edge(ll a,ll b){
	Next[++idx]=head[a],head[a]=idx,ver[idx]=b;
	return;
}

void getSiz(ll p){
	siz[p]=w[p]%mod;
	for (ll i=head[p];i;i=Next[i]){
		getSiz(ver[i]);siz[p]+=siz[ver[i]],siz[p]%=mod;
	}
	return;
}

void getRes(ll p){
	ll s=siz[p];
	res+=mul(mul(w[p],w[p]),s*2-w[p]);
	for (ll i=head[p];i;i=Next[i]){
		res+=mul(mul(siz[ver[i]],s-siz[ver[i]]-w[p]),w[p]);
		getRes(ver[i]);
	}
	return;
}

int main(){
	freopen("asm_algo.in","r",stdin);
	freopen("asm_algo.out","w",stdout);
	
	ll pt;
	ll si;
	scanf("%d %lld",&n,&w[1]);
	for (ll i=2;i<=n;i++){
		scanf("%d %lld",&pt,&si);
		edge(pt,i);fat[i]=pt,w[i]=si;
	}
	getSiz(1);
	getRes(1);
	printf("%lld",res%mod);
	
	return 0;
}