比赛 2024暑假C班集训B 评测结果 AAAAAAEEEE
题目名称 Asm.Def的基本算法 最终得分 60
用户昵称 123 运行时间 0.993 s
代码语言 C++ 内存使用 4.32 MiB
提交时间 2024-07-11 10:43:39
显示代码纯文本
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N=100010,Mod=1e9+7,M=1010;
  4. int flag[N],n,w[N],p[N],dp[M][M];
  5. long long ret=0;
  6. int LCA(int a,int b)
  7. {
  8. for (int i=a;i;i=p[i])
  9. {
  10. flag[i]=1;
  11. }
  12. int cnt=0;
  13. for (int i=b;i;i=p[i])
  14. {
  15. if (flag[i])
  16. {
  17. cnt=i;
  18. break;
  19. }
  20. }
  21. for (int i=a;i;i=p[i])
  22. {
  23. flag[i]=0;
  24. }
  25. return cnt;
  26. }
  27. int main() {
  28. freopen("asm_algo.in","r",stdin);
  29. freopen("asm_algo.out","w",stdout);
  30. scanf("%d%d",&n,&w[1]);
  31. for (int i=2;i<=n;i++)
  32. {
  33. scanf("%d%d",&p[i],&w[i]);
  34. }
  35. for (int i=1;i<=n;i++)
  36. {
  37. for (int j=1;j<=n;j++)
  38. {
  39. if (dp[j][i])
  40. {
  41. ret+=dp[j][i];
  42. ret%=Mod;
  43. continue;
  44. }
  45. dp[i][j]=w[i]*w[j]*w[LCA(i,j)];
  46. dp[i][j]%=Mod;
  47. ret+=dp[i][j];
  48. ret%=Mod;
  49. }
  50. }
  51. cout<<ret;
  52. }