比赛 2024暑假C班集训B 评测结果 AAAAAAAAWW
题目名称 Asm.Def的基本算法 最终得分 80
用户昵称 wzh0425 运行时间 0.106 s
代码语言 C++ 内存使用 4.09 MiB
提交时间 2024-07-11 10:40:27
显示代码纯文本
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long n,w[100005],hd[200005],nxt[200005],ver[200005],idx,s[100005],res;
  4. void add(long long x,long long y){
  5. ver[++idx]=y;
  6. nxt[idx]=hd[x];
  7. hd[x]=idx;
  8. }
  9. long long dfs(long long x){
  10. long long sum=0;
  11. for (long long i=hd[x];i;i=nxt[i]){
  12. long long y=ver[i];
  13. sum+=dfs(y);
  14. }
  15. s[x]=sum+w[x];
  16. return s[x];
  17. }
  18. long long mul(long long x,long long y){
  19. return x*y%1000000007;
  20. }
  21. void getRes(long long p){
  22. long long sz=s[p];
  23. res+=mul(mul(w[p],w[p]),sz*2-w[p]);
  24. for (long long i=hd[p];i;i=nxt[i]){
  25. res+=mul(mul(s[ver[i]],sz-s[ver[i]]-w[p]),w[p]);
  26. getRes(ver[i]);
  27. }
  28. return;
  29. }
  30. int main(){
  31. freopen("asm_algo.in","r",stdin);
  32. freopen("asm_algo.out","w",stdout);
  33. scanf("%d%d",&n,&w[1]);
  34. for (long long i=2;i<=n;i++){
  35. long long x;
  36. scanf("%d%d",&x,&w[i]);
  37. add(x,i);
  38. }
  39. dfs(1);
  40. getRes(1);
  41. cout<<res%1000000007;
  42. return 0;
  43. }