Advertisement
MinhNGUYEN2k4

Untitled

Sep 4th, 2021
977
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 100005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, root, q;
  28. vector<int> g[N];
  29. int c[N];
  30. set<int> s[N];
  31. int res[N];
  32.  
  33. void readfile()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0);cout.tie(0);
  37.     if (fopen(Task".inp","r"))
  38.     {
  39.         freopen(Task".inp","r",stdin);
  40.         //freopen(Task".out","w",stdout);
  41.     }
  42.     cin >> n >> q >> root;
  43.     for(int i=1; i<n; i++){
  44.         int u, v;
  45.         cin >> u >> v;
  46.         g[u].pb(v);
  47.         g[v].pb(u);
  48.     }
  49.     for(int i=1; i<=n; i++) cin >> c[i];
  50. }
  51.  
  52. void dfs(int u, int par){
  53.     s[u].insert(c[u]);
  54.     for(auto v : g[u]){
  55.         if (v!=par){
  56.             dfs(v,u);
  57.             if (s[v].size()>s[u].size()) swap(s[u],s[v]);
  58.             for(int i : s[v]) s[u].insert(i);
  59.         }
  60.     }
  61.     res[u] = s[u].size();
  62. }
  63.  
  64. void proc()
  65. {
  66.     dfs(root,root);
  67.     while (q--){
  68.         int S; cin >> S;
  69.         cout << res[S] << '\n';
  70.     }
  71. }
  72.  
  73. signed main()
  74. {
  75.     readfile();
  76.     proc();
  77.     return 0;
  78. }
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement