记录编号	382605	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的基本算法	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2017-03-14 10:07:20	内存使用	2.20 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;
}
const int maxn=100005,INF=1000*1000*1000+7;
struct Rabit_tree{int to,next;}e[maxn];
int n,head[maxn],len=1,c[maxn],ans=0,w[maxn];
void Set(int prt,int son){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len;
}
#define to e[i].to
void Dfs(int rt){
	int i,tmp;
	for(i=head[rt];i;i=e[i].next){
		Dfs(to),w[rt]+=w[to];
		if(w[rt]>=INF)w[rt]-=INF;
	}
	for(i=head[rt];i;i=e[i].next){
		tmp=w[rt]-w[to];if(tmp<0)tmp+=INF;
		ans+=((w[to]*1ll*tmp)%INF*1ll*c[rt])%INF;
		if(ans>=INF)ans-=INF;
	}		
	tmp=((c[rt]*1ll*w[rt])%INF*1ll*c[rt])%INF;
	ans+=tmp;if(ans>=INF)ans-=INF;
	w[rt]+=c[rt];if(w[rt]>=INF)w[rt]-=INF;
	tmp=((c[rt]*1ll*w[rt])%INF*1ll*c[rt])%INF;
	ans+=tmp;if(ans>=INF)ans-=INF;
}
int main(){
	freopen("asm_algo.in","r",stdin);freopen("asm_algo.out","w",stdout);
	R_int(n),R_int(c[1]);int i,x;
	for(i=2;i<=n;i++)R_int(x),Set(x,i),R_int(c[i]);
	Dfs(1);printf("%d\n",ans);
}