Advertisement
jiteshrao

Untitled

Nov 28th, 2020
786
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5;
  5.  
  6. vector<int> v[N];
  7. int colour[N];
  8. int parent[N];
  9.  
  10. void dfs1(int sv, int par)
  11. {
  12.     parent[sv] = par;
  13.     for(int x : v[sv])
  14.     {
  15.         if(x == par)
  16.         {
  17.             continue;
  18.         }
  19.         dfs1(x, sv);
  20.     }
  21. }
  22.  
  23. void dfs2(int sv, set<int> & s)
  24. {
  25.     s.insert(colour[sv]);
  26.     for(int x : v[sv])
  27.     {
  28.         if(x == parent[sv])
  29.         {
  30.             continue;
  31.         }
  32.         dfs2(x, s);
  33.     }
  34. }
  35.  
  36. int32_t main()
  37. {
  38.     ios_base:: sync_with_stdio(false);
  39.     cin.tie(NULL);
  40.     cout.tie(NULL);
  41.     #ifndef ONLINE_JUDGE
  42.       freopen("input.txt", "r", stdin);
  43.       freopen("output.txt", "w", stdout);
  44.     #endif
  45.     int n, root, query;
  46.     cin >> n >> query >> root;
  47.     for(int i = 0; i < n - 1; i++)
  48.     {
  49.         int a, b;
  50.         cin >> a >> b;
  51.         v[a].push_back(b);
  52.         v[b].push_back(a);
  53.     }
  54.     for(int i = 1; i <= n; i++)
  55.     {
  56.         cin >> colour[i];
  57.     }
  58.     dfs1(root, 0);
  59.     for(int i = 1; i <= query; i++)
  60.     {
  61.         int node;
  62.         cin >> node;
  63.         set<int> s;
  64.         dfs2(node, s);
  65.         cout << (int)s.size() << endl;
  66.     }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement