fork(2) download
  1. //tonynater - HackerRank 2014
  2.  
  3. #include <algorithm>
  4. #include <bitset>
  5. #include <cassert>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <fstream>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <list>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <stack>
  17. #include <string>
  18. #include <vector>
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <string.h>
  22.  
  23. using namespace std;
  24.  
  25. #define sz(x) ((int) x.size())
  26.  
  27. typedef long double ld;
  28. typedef long long ll;
  29. typedef pair<int, int> pii;
  30.  
  31. const double pi = acos(-1);
  32. const double tau = 2*pi;
  33. const double epsilon = 1e-6;
  34.  
  35. const int MAX_N = 100100;
  36.  
  37. int N, M, R;
  38.  
  39. vector<int> adj[MAX_N];
  40.  
  41. int color[MAX_N];
  42.  
  43. vector<int> children[MAX_N];
  44. void root(int u, int parent)
  45. {
  46. for(int i = 0; i < sz(adj[u]); i++)
  47. if(adj[u][i] != parent)
  48. {
  49. root(adj[u][i], u);
  50. children[u].push_back(adj[u][i]);
  51. }
  52. }
  53.  
  54. vector<int> inorder;
  55. void order(int u)
  56. {
  57. for(int i = 0; i < sz(children[u]); i++)
  58. order(children[u][i]);
  59. inorder.push_back(u);
  60. }
  61.  
  62. int nDistinct[MAX_N];
  63. int idx[MAX_N];
  64. set<int> subtree[MAX_N];
  65. void countElements(int u)
  66. {
  67. int mxChild = 0, big = u;
  68. for(int i = 0; i < sz(children[u]); i++)
  69. if(sz(subtree[idx[children[u][i]]]) > mxChild)
  70. {
  71. mxChild = sz(subtree[idx[children[u][i]]]);
  72. big = idx[children[u][i]];
  73. }
  74.  
  75. for(int i = 0; i < sz(children[u]); i++)
  76. if(idx[children[u][i]] != big)
  77. {
  78. for(set<int>::const_iterator it = subtree[idx[children[u][i]]].begin(); it != subtree[idx[children[u][i]]].end(); it++)
  79. subtree[big].insert(*it);
  80. subtree[idx[children[u][i]]].clear();
  81. }
  82. subtree[big].insert(color[u]);
  83.  
  84. nDistinct[u] = sz(subtree[big]);
  85. idx[u] = big;
  86. }
  87.  
  88. int main()
  89. {
  90. ios_base::sync_with_stdio(0);
  91. cin.tie(NULL);
  92.  
  93. cin >> N >> M >> R;
  94. --R;
  95.  
  96. for(int i = 0; i < N-1; i++)
  97. {
  98. int u, v;
  99. cin >> u >> v;
  100. --u; --v;
  101.  
  102. adj[u].push_back(v);
  103. adj[v].push_back(u);
  104. }
  105.  
  106. for(int i = 0; i < N; i++)
  107. cin >> color[i];
  108.  
  109. root(R, -1);
  110. order(R);
  111.  
  112. for(int i = 0; i < sz(inorder); i++)
  113. countElements(inorder[i]);
  114.  
  115. for(int i = 0; i < M; i++)
  116. {
  117. int s;
  118. cin >> s;
  119. --s;
  120.  
  121. cout << nDistinct[s] << '\n';
  122. }
  123.  
  124. return 0;
  125. }
Success #stdin #stdout 0s 9304KB
stdin
4 2 1
1 2
2 4
2 3
10
20
20
30
1
2
stdout
3
2