比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
100 |
用户昵称 |
AntiLeaf |
运行时间 |
0.147 s |
代码语言 |
C++ |
内存使用 |
3.69 MiB |
提交时间 |
2016-10-15 18:38:35 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=100010;
const LL p=1000000007ll;
namespace mine{
template<class T>inline void readint(T &__x){
static int __c;
//static bool __neg;
__x=0;
//__neg=false;
do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
/*if(__c=='-'){
__neg=true;
__c=getchar();
}*/
for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
//if(__neg)__x=-__x;
}
template<class T>inline void putint(T __x){
static int __a[40],__i,__j;
//static bool __neg;
//__neg=__x<0;
//if(__neg)__x=-__x;
__i=0;
do{
__a[__i++]=__x%(T)10^(T)48;
__x/=10;
}while(__x);
//if(__neg)putchar('-');
for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
}
}
using namespace mine;
struct edge{
int to,prev;
}e[maxn<<1];
void insert(int,int);
void dfs(int);
LL ans=0ll;
int n,len=0,last[maxn]={0},prt[maxn]={0},x,y;
LL w[maxn],sum[maxn];
int main(){
#define MINE
#ifdef MINE
freopen("asm_algo.in","r",stdin);
freopen("asm_algo.out","w",stdout);
#endif
readint(n);
readint(w[1]);
for(int i=2;i<=n;i++){
readint(prt[i]);
readint(w[i]);
insert(prt[i],i);
}
dfs(1);
ans<<=1;
for(int i=1;i<=n;i++)ans=(ans+w[i]*w[i]%p*w[i]%p)%p;
putint(ans);
#ifndef MINE
printf("\n--------------------DONE--------------------\n");
for(;;);
#endif
return 0;
}
void insert(int x,int y){
e[++len].to=y;
e[len].prev=last[x];
last[x]=len;
}
void dfs(int x){
sum[x]=w[x];
for(int i=last[x];i;i=e[i].prev){
dfs(e[i].to);
ans=(ans+(LL)sum[x]*(LL)sum[e[i].to]%p*(LL)w[x]%p)%p;
sum[x]=(sum[x]+sum[e[i].to])%p;
}
}