//gm --- akezhon
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #define int long long
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define tm (tl+tr)/2
#define TL v+v, tl, tm
#define TR v+v+1, tm+1, tr
#define DA l <= tl && tr <= r
#define NET r < tl || tr < l
#define double long double
using namespace std;
const int N=2e5+7;
const int M=1e9+7;
const int inf=1e9;
int c[N], tin[N], tout[N], eul[N], sz[N], ans[N], big[N];
vector <pair<int*, int>> rb;
vector <int> g[N];
int n, timer, cnt;
int ok[N];
void dfs(int v=1, int p=0){
tin[v] = ++timer;
eul[timer] = v;
sz[v] = 1;
for(int to : g[v]){
if(to == p)continue;
dfs(to, v);
sz[v] += sz[to];
if(sz[to] > sz[big[v]])big[v] = to;
}
tout[v] = timer;
}
void roll(int &x){
rb.push_back({&x, x});
}
void upd(int v){
if(!ok[c[v]]){
roll(ok[c[v]]);
roll(cnt);
cnt++;
ok[c[v]] = 1;
}
}
void go(int v=1, int p=0, int cl=0){
int temp = rb.size();
for(int to: g[v]){
if(to != p && to != big[v])go(to, v, 1);
}
if(big[v])go(big[v], v, 0);
upd(v);
for(int to: g[v]){
if(to == p || to == big[v])continue;
for(int i = tin[to]; i <= tout[to]; i++)upd(eul[i]);
}
ans[v] = cnt;
if(cl){
while(rb.size()>temp){
*(rb.back().F) = rb.back().S;
rb.pop_back();
}
}
}
void AlemAmenov(){
cin >> n;
map<int, int>mp;
int c=0;
for(int i=1; i <= n; i++){
cin >> c[i];
if(!mp[c[i]])mp[c[i]] = ++c;
c[i] = mp[c[i]];
}
for(int i=1; i < n; i++){
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
dfs();
go();
for(int i=1; i <= n; i++){
cout << ans[i] << ' ';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("justforfood.in", "r", stdin);
// freopen("justforfood.out", "w", stdout);
int RealName=1;
// cin >> RealName;
// int C=0;
while(RealName--){
// cout << "Case " << ++C << ":\n";
AlemAmenov();
}
return 0;
}
Compilation message
rot.cpp: In function 'void go(int, int, int)':
rot.cpp:63:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
63 | while(rb.size()>temp){
| ~~~~~~~~~^~~~~
rot.cpp: In function 'void AlemAmenov()':
rot.cpp:75:11: error: invalid types 'int[int]' for array subscript
75 | cin >> c[i];
| ^
rot.cpp:76:11: error: invalid types 'int[int]' for array subscript
76 | if(!mp[c[i]])mp[c[i]] = ++c;
| ^
rot.cpp:76:20: error: invalid types 'int[int]' for array subscript
76 | if(!mp[c[i]])mp[c[i]] = ++c;
| ^
rot.cpp:77:4: error: invalid types 'int[int]' for array subscript
77 | c[i] = mp[c[i]];
| ^
rot.cpp:77:14: error: invalid types 'int[int]' for array subscript
77 | c[i] = mp[c[i]];
| ^
