比赛 noip2016普及练习2 评测结果 AAAAAAAA
题目名称 保卫钓鱼岛! 最终得分 100
用户昵称 明天 运行时间 0.063 s
代码语言 C++ 内存使用 1.24 MiB
提交时间 2016-11-07 20:28:45
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. struct node
  7. {
  8. int x,next;
  9. };
  10.  
  11. const int maxn=10000+1;
  12. const int maxm=100000+1;
  13.  
  14. int n,m;
  15. int h[maxn],len;
  16. node table[maxm];
  17.  
  18. int x,y,z;
  19. bool used[maxn];
  20. int w[maxn],depth[maxn],father[maxn];
  21. int ans;
  22. long long total;
  23.  
  24. void dfs(int x);
  25. inline int getint()
  26. {
  27. int x=0;
  28. char ch=getchar();
  29. while (ch<'0' || ch>'9')
  30. ch=getchar();
  31. while (ch>='0' && ch<='9')
  32. {
  33. x=x*10+ch-'0';
  34. ch=getchar();
  35. }
  36. return x;
  37. }
  38. inline void add1(int i, int j)
  39. {
  40. len++;
  41. table[len].x=j; table[len].next=h[i];
  42. h[i]=len;
  43. }
  44. int main()
  45. {
  46. freopen("diaoyu.in","r",stdin);
  47. freopen("diaoyu.out","w",stdout);
  48. scanf("%d%d",&n,&m);
  49. for (int k=1; k<n; k++)
  50. {
  51. x=getint(); y=getint(); z=getint();
  52. add1(x,y);
  53. w[y]=z; father[y]=x;
  54. }
  55. dfs(1);
  56. for (int k=1; k<=m; k++)
  57. {
  58. x=getint(); y=getint();
  59. if (x==y) continue;
  60. int t=0;;
  61. while (depth[y]>depth[x])
  62. {
  63. t+=w[y];
  64. y=father[y];
  65. }
  66. if (x==y)
  67. {
  68. total+=t; ans++;
  69. }
  70. }
  71. cout<<ans<<endl;
  72. cout<<total<<endl;
  73. return 0;
  74. }
  75.  
  76. void dfs(int x)
  77. {
  78. int p=h[x];
  79. while (p)
  80. {
  81. int u=table[p].x;
  82. if (!used[u])
  83. {
  84. used[u]=true; depth[u]=depth[x]+1;
  85. dfs(u);
  86. }
  87. p=table[p].next;
  88. }
  89. }