比赛 “Asm.Def战记之太平洋”杯 评测结果 AWWWWWWWWT
题目名称 Asm.Def的基本算法 最终得分 10
用户昵称 Fmuckss 运行时间 1.104 s
代码语言 C++ 内存使用 3.80 MiB
提交时间 2015-11-02 11:58:24
显示代码纯文本
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define maxn 100000
#define mo 1000000007
using namespace std;
typedef long long LL;
LL n,w[maxn],wtot[maxn];
bool insta[maxn];
int stack[maxn],top;
LL ans[maxn];
//int getfa(int a){return fa[a]==a ? a:fa[a]=getfa(fa[a]);}
struct node{
	vector<int> ne;
}ns[maxn];
void gettot(int i){
	for(int j=0;j<ns[i].ne.size();j++){
		int tmp=ns[i].ne[j];
		gettot(tmp);
		wtot[i]+=wtot[tmp];
	}
	wtot[i]+=w[i];
//	printf("%d:%lld\n",i,wtot[i]);
}
LL tarjan(int i){
	for(int j=0;j<ns[i].ne.size();j++){
		int tmp=ns[i].ne[j];
		gettot(tmp);
		wtot[i]+=wtot[tmp];
	}
}
LL solve(int i){
	ans[i]+=((w[i]%mo)*(w[i]%mo)*(w[i]%mo))%mo;
	int tmptot=0;
	for(int j=0;j<ns[i].ne.size();j++){
		tmptot+=w[ns[i].ne[j]];
	}
	for(int j=0;j<ns[i].ne.size();j++){
		int tmp=ns[i].ne[j];
		ans[i]+=(((((w[i]%mo)*((wtot[i]-wtot[tmp])%mo))*(wtot[tmp])%mo))%mo)%mo;
		ans[i]+=((w[i]%mo)*(((tmptot-w[tmp])%mo)*w[tmp]))%mo;
		ans[i]+=w[i]*w[i]*w[tmp];
		ans[i]+=solve(tmp)%mo;
		ans[i]%=mo;
	}
	return ans[i]%mo;
}
void read(){
	scanf("%lld %lld",&n,&w[1]);
	for(int i=2;i<=n;i++){
		LL a,b;
		scanf("%lld %lld",&a,&w[i]);
		ns[a].ne.push_back(i);
	}
}
int main(){
	freopen("asm_algo.in","r",stdin);
	freopen("asm_algo.out","w",stdout);
	read();
	gettot(1);
	printf("%lld",solve(1));
	return 0;
}