Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n,s[200005];
- set<int>r[200005];
- vector<int>v[200005];
- bool vz[200005];
- void dfs(int x){
- vz[x]=true;
- for(int i=0;i<(int)v[x].size();i++){
- if(vz[v[x][i]])continue;
- dfs(v[x][i]);
- if(r[v[x][i]].size()>r[x].size())swap(r[v[x][i]],r[x]);
- for(int y:r[v[x][i]])r[x].insert(y);
- }
- s[x]=r[x].size();
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cin>>n;
- for(int i=1;i<=n;i++){
- int x;
- cin>>x;
- r[i].insert(x);
- }
- for(int i=1;i<n;i++){
- int a,b;
- cin>>a>>b;
- v[a].push_back(b);
- v[b].push_back(a);
- }
- dfs(1);
- for(int i=1;i<=n;i++)cout<<s[i]<<" ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement