比赛 |
“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;
}