#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
int it[200001];
vector<int> adj[200001];
vector<int> adj2[200001];
int vis[200001];
int val[200001];
int ans[200001];
pair<int,int> ma={-1,-1};
int par2[200001];
void dfs(int no,int par=-1,int levv=0){
ma=max(ma,{levv,no});
par2[no]=par;
for(auto j:adj[no]){
if(j!=par){
dfs(j,no,levv+1);
}
}
}
void dfs2(int no,int par=-1,int levv=0){
ma=max(ma,{levv,no});
par2[no]=par;
for(auto j:adj2[no]){
if(j!=par){
dfs2(j,no,levv+1);
}
}
}
int pp;
/*void dfs3(int no,int par=-1,int levv=0){
ma=max(ma,{levv,no});
par2[no]=par;
ans[no]=pp;
for(auto j:adj2[no]){
if(j!=par){
dfs3(j,no,levv+1);
}
}
}*/
map<int,int> ee;
int co=0;
void add(int i){
ee[it[i]]++;
if(ee[it[i]]==1){
co++;
}
}
void remove(int i){
ee[it[i]]--;
if(ee[it[i]]==0){
co--;
}
}
//set<pair<int,int>> zz;
int ma2[200001];
void dfs4(int no,int par=-1,int lev=0){
ma2[no]=0;
for(auto j:adj2[no]){
if(j!=par){
dfs4(j,no,lev+1);
ma2[no]=max(ma2[no],ma2[j]+1);
}
}
}
set<pair<int,int>> zz;
int ne[200001];
vector<pair<int,int>> pre2[200001];
void dfs5(int no,int par=-1,int lev=0,int zz2=1){
vector<pair<int,int>> mm;
//cout<<no<<";";
for(auto j:adj2[no]){
if(j!=par){
mm.pb({ma2[j],j});
}
}
sort(mm.begin(),mm.end());
reverse(mm.begin(),mm.end());
vector<pair<int,int>> kk;
add(no);
zz.insert({lev,no});
int ind3=-1;
for(auto j:mm){
ind3++;
int ne=-1;
if(ind3==0){
if(mm.size()>=2){
ne=mm[1].a;
}
}
else if(ind3==1){
ne=mm[0].a;;
}
if(ne>=0){
ne++;
auto jj=zz.lower_bound({lev-ne,-1});
vector<pair<int,int>> ll;
while(jj!=zz.end()){
if((*jj).a>=lev){
break;
}
remove((*jj).b);
ll.pb(*jj);
jj++;
}
for(auto ii:ll){
kk.pb(ii);
zz.erase(ii);
}
}
dfs5(j.b,no,lev+1,ind3==0);
}
if(mm.size()){
ne[no]=mm[0].b;
}
else{
ne[no]=-1;
}
if(mm.size()==1){
int ne=mm[0].a+1;
auto jj=zz.lower_bound({lev-ne,-1});
vector<pair<int,int>> ll;
while(jj!=zz.end()){
if((*jj).a>=lev){
break;
}
remove((*jj).b);
ll.pb(*jj);
jj++;
}
for(auto ii:ll){
kk.pb(ii);
zz.erase(ii);
}
}
pre2[no]=kk;
if(zz.find({lev,no})!=zz.end()){
zz.erase({lev,no});
remove(no);
}
ans[no]=co;
//lev-1 to lev-ma[no]
if(zz2==1){
int cur=no;
while(cur>=0){
for(auto j:pre2[no]){
if(j.a<lev){
zz.insert(j);
add(j.b);
}
}
break;
cur=ne[cur];
}
}
}
int ha=0;
void solve(vector<int> ss){
set<pair<int,int>> tt;
ee.clear();
co=0;
//map of present colours
int ind=ss.size();
for(int i=0;i<ss.size();i++){
tt.insert({i,ss[i]});
}
for(int i=ss.size()-1;i>=0;i--){
auto j=tt.lower_bound({i+1,-1});
vector<pair<int,int>> kk;
while(j!=tt.end()){
if((*j).a>i+val[ss[i]]){
break;
}
if((*j).a>=ind){
remove((*j).b);
}
kk.pb(*j);
j++;
/*if(ss[0]==1){
cout<<(*j).b<<"?"<<endl;
}*/
}
for(auto j:kk){
tt.erase(j);
}
if(i<(int)(ss.size())-i-1){
int ind2=2*i+1;
while(ind>ind2){
ind--;
if(tt.find({ind,ss[ind]})!=tt.end()){
add(ss[ind]);
}
}
ans[ss[i]]=co;
//continue;
/* if(ss[i]==0){
for(auto jj:ee){
cout<<jj.a<<",,"<<jj.b<<endl;
}
}*/
dfs4(ss[i]);
/* if(ss[i]==0){
cout<<ma2[ss[i]]<<"?"<<endl;
}*/
dfs5(ss[i]);
// cout<<endl;
//ans[ss[i]]=co;
}
if(i==(int)ss.size()-i-1 and ha==0){
ha=1;
dfs4(ss[i]);
dfs5(ss[i]);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin>>n>>m;
for(int i=0;i<n-1;i++){
int aa,bb;
cin>>aa>>bb;
aa--;
bb--;
adj[aa].pb(bb);
adj[bb].pb(aa);
}
for(int i=0;i<n;i++){
cin>>it[i];
}
dfs(0);
int x=ma.b;
ma={-1,-1};
dfs(x);
dfs2(x);
vector<int> ss;
int cur=ma.b;
while(true){
ss.pb(cur);
cur=par2[cur];
if(cur==-1){
break;
}
}
for(auto j:ss){
vis[j]=1;
}
for(int i=0;i<n;i++){
for(auto j:adj[i]){
if(vis[i]+vis[j]<2){
adj2[i].pb(j);
}
}
}
for(auto j:ss){
ma={-1,-1};
dfs2(j);
val[j]=ma.a;
//cout<<j<<":"<<ma.a<<endl;
}
solve(ss);
reverse(ss.begin(),ss.end());
solve(ss);
/* for(auto j:ss){
pp=ans[j];
dfs3(j);
}*/
for(int i=0;i<n;i++){
cout<<ans[i]<<endl;
}
return 0;
}
Compilation message
joi2019_ho_t5.cpp: In function 'void solve(std::vector<int>)':
joi2019_ho_t5.cpp:179:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for(int i=0;i<ss.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
28732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
333 ms |
41044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
