比赛 “Asm.Def战记之太平洋”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的基本算法 最终得分 100
用户昵称 fyb 运行时间 0.206 s
代码语言 C++ 内存使用 2.68 MiB
提交时间 2015-11-02 11:12:01
显示代码纯文本
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. #define NMAX 100000
  7. #define P 1000000007
  8.  
  9. vector<int> g[NMAX+1];
  10. long long w[NMAX+1],sum[NMAX+1];
  11.  
  12. long long dfs(int ind){
  13. long long ans=0,s,tmp=0;
  14. int tn;
  15. int i;
  16.  
  17. s=w[ind];
  18. for(i=0;i<g[ind].size();i++){
  19. tn=g[ind][i];
  20. ans=(ans+dfs(tn))%P;
  21. tmp=(tmp+(s*sum[tn])%P)%P;
  22. s=(s+sum[tn])%P;
  23. }
  24. tmp=((tmp*2)%P+(w[ind]*w[ind])%P)%P;
  25. sum[ind]=s;
  26. // printf("%lld\n",sum[ind]);
  27. return ans=(ans+(tmp*w[ind])%P)%P;
  28. }
  29.  
  30. int main(){
  31. int n;
  32. int tp;
  33. int i;
  34.  
  35. freopen("asm_algo.in","r",stdin);
  36. freopen("asm_algo.out","w",stdout);
  37.  
  38. scanf("%d%lld",&n,w+1);
  39. for(i=2;i<=n;i++){
  40. scanf("%d%lld",&tp,w+i);
  41. g[tp].push_back(i);
  42. }
  43.  
  44. printf("%lld",dfs(1));
  45. return 0;
  46. }
  47.