SHARE
TWEET

Untitled

a guest Dec 16th, 2018 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5. const int N = 5e5 + 5;
  6. int c[N];
  7. vector<int> gr[N];
  8. int dp[N];
  9. set<int> q[N];
  10. int idx[N];
  11. void dfs(int x , int p) {
  12.     for (int i : gr[x]) {
  13.         if (i != p) {
  14.             dfs(i , x);
  15.         }
  16.     }
  17.     if (c[x] != 0) {
  18.         q[x].insert(c[x]);
  19.         idx[x] = x;
  20.         dp[x] = 1;
  21.     } else {
  22.         for (int i : gr[x]) {
  23.             if (i == p) continue;
  24.             if (q[idx[x]].size() < q[idx[i]].size()) idx[x] = idx[i];
  25.         }
  26.         for (int i : gr[x]) {
  27.             if (idx[x] == idx[i] || i == p) continue;
  28.             for (int j : q[idx[i]]) {
  29.                 q[idx[x]].insert(j);
  30.             }
  31.         }
  32.         dp[x] = q[idx[x]].size();
  33.     }
  34.  
  35. }
  36.  
  37. int32_t main()
  38. {
  39.     ios_base::sync_with_stdio(0);
  40.     int n , k;
  41.     cin>>n>>k;
  42.     for (int i = 0; i < n ; ++ i) {
  43.         cin>>c[i];
  44.     }
  45.     for (int i = 1 ; i < n ; ++ i) {
  46.         int vv ;
  47.         cin>>vv;
  48.         --vv;
  49.         gr[vv].push_back(i);
  50.         gr[i].push_back(vv);
  51.     }
  52.     dfs(0, -1);
  53.     for (int i = 0; i < n ; ++ i) {
  54.         cout<<dp[i]<<' ';
  55.     }
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top