tuki2501

Coloring Tree

Oct 31st, 2020
850
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ----------- define --------------
  5. // #define int long long
  6. #define vi vector<int>
  7. #define ii pair<int,int>
  8. #define fi first
  9. #define sc second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pqueue priority_queue
  13. #define popcnt __builtin_popcount
  14. #define getBit(x, k) ((x >> k) & 1)
  15. #define xorBit(x, k) (x ^ (1 << k))
  16. #define siz(x) (int)((x).size())
  17. #define all(x) (x).begin(),(x).end()
  18. // ---------------------------------
  19.  
  20. const int N = 100005;
  21.  
  22. vector<int> adj[N];
  23. int num[N], res[N];
  24. set<int> s[N];
  25.  
  26. void dfs(int i, int p) {
  27.   for (auto &j : adj[i]) {
  28.     if (j == p) continue;
  29.     dfs(j, i);
  30.     if (s[i].size() < s[j].size()) {
  31.       swap(s[i], s[j]);
  32.     }
  33.     for (auto &k : s[j]) {
  34.       s[i].insert(k);
  35.     }
  36.   }
  37.   s[i].insert(num[i]);
  38.   res[i] = s[i].size();
  39. }
  40.  
  41. void Main() {
  42.   int n, m, r;
  43.   cin >> n >> m >> r;
  44.   for (int i = 1; i < n; i++) {
  45.     int u, v;
  46.     cin >> u >> v;
  47.     adj[u].push_back(v);
  48.     adj[v].push_back(u);
  49.   }
  50.   for (int i = 1; i <= n; i++) {
  51.     cin >> num[i];
  52.   }
  53.   dfs(r, 0);
  54.   for (int i = 1; i <= m; i++) {
  55.     int x; cin >> x;
  56.     cout << res[x] << '\n';
  57.   }
  58. }
  59.  
  60. signed main() {
  61. #ifdef _DEBUG
  62.   // freopen("in" , "r", stdin );
  63.   cerr << "- ---- -- ----- <3\n";
  64. #endif
  65.   cin.tie(0)->sync_with_stdio(0);
  66.   int T = 1;
  67.   // cin >> T;
  68.   while (T--) Main();
  69. }
RAW Paste Data