fork(2) download
copy 
  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
comments (?)
stdin
copy 
4 2 1
1 2
2 4
2 3
10
20
20
30
1
2
stdout
copy 
3
2
https://ideone.com/Lje1R5
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!