Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int N = 5e5 + 5;
- int c[N];
- vector<int> gr[N];
- int dp[N];
- set<int> q[N];
- int idx[N];
- void dfs(int x , int p) {
- for (int i : gr[x]) {
- if (i != p) {
- dfs(i , x);
- }
- }
- if (c[x] != 0) {
- q[x].insert(c[x]);
- idx[x] = x;
- dp[x] = 1;
- } else {
- for (int i : gr[x]) {
- if (i == p) continue;
- if (q[idx[x]].size() < q[idx[i]].size()) idx[x] = idx[i];
- }
- for (int i : gr[x]) {
- if (idx[x] == idx[i] || i == p) continue;
- for (int j : q[idx[i]]) {
- q[idx[x]].insert(j);
- }
- }
- dp[x] = q[idx[x]].size();
- }
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- int n , k;
- cin>>n>>k;
- for (int i = 0; i < n ; ++ i) {
- cin>>c[i];
- }
- for (int i = 1 ; i < n ; ++ i) {
- int vv ;
- cin>>vv;
- --vv;
- gr[vv].push_back(i);
- gr[i].push_back(vv);
- }
- dfs(0, -1);
- for (int i = 0; i < n ; ++ i) {
- cout<<dp[i]<<' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement