比赛 |
2024暑假C班集训B |
评测结果 |
AAAAAAAAWW |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
80 |
用户昵称 |
wzh0425 |
运行时间 |
0.106 s |
代码语言 |
C++ |
内存使用 |
4.09 MiB |
提交时间 |
2024-07-11 10:40:27 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,w[100005],hd[200005],nxt[200005],ver[200005],idx,s[100005],res;
void add(long long x,long long y){
ver[++idx]=y;
nxt[idx]=hd[x];
hd[x]=idx;
}
long long dfs(long long x){
long long sum=0;
for (long long i=hd[x];i;i=nxt[i]){
long long y=ver[i];
sum+=dfs(y);
}
s[x]=sum+w[x];
return s[x];
}
long long mul(long long x,long long y){
return x*y%1000000007;
}
void getRes(long long p){
long long sz=s[p];
res+=mul(mul(w[p],w[p]),sz*2-w[p]);
for (long long i=hd[p];i;i=nxt[i]){
res+=mul(mul(s[ver[i]],sz-s[ver[i]]-w[p]),w[p]);
getRes(ver[i]);
}
return;
}
int main(){
freopen("asm_algo.in","r",stdin);
freopen("asm_algo.out","w",stdout);
scanf("%d%d",&n,&w[1]);
for (long long i=2;i<=n;i++){
long long x;
scanf("%d%d",&x,&w[i]);
add(x,i);
}
dfs(1);
getRes(1);
cout<<res%1000000007;
return 0;
}