#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 2000000000
#define N 200005
#define MOD 998244353
using namespace std;
int n,m;
int mxd[N][2],der[N];
int ans[N],c[N],deep[N];
int s[N];
int sz;
int tot_op;
int cntd;
int cnt[N];
vector<int> v[N];
struct diameter_finder {
int l,r;
int mx;
void dfs(int node,int ata,int len) {
if(len>mx) {
mx=len;
l=node;
}
for(int i:v[node]) {
if(i==ata) continue ;
dfs(i,node,len+1);
}
}
void find() {
mx=0;
dfs(1,0,0);
r=l;
mx=0;
dfs(r,0,0);
}
} dia;
void rollback(vector<int>& roll) {
while(!roll.empty()) {
int x=roll.back();
roll.ppb();
++tot_op;
s[++sz]=x;
cntd+=(cnt[c[x]]==0);
cnt[c[x]]++;
}
}
void add(int node) {
s[++sz]=node;
++tot_op;
cntd+=(cnt[c[node]]==0);
cnt[c[node]]++;
}
void del(vector<int>& roll,int cur) {
while(sz && cur<=der[s[sz]]) {
++tot_op;
roll.pb(s[sz]);
cnt[c[s[sz]]]--;
cntd-=(cnt[c[s[sz]]]==0);
--sz;
}
}
void upd(int node,int nd) {
if(mxd[node][1]<nd) mxd[node][1]=nd;
if(mxd[node][1]>mxd[node][0]) swap(mxd[node][1],mxd[node][0]);
}
vector<int> temp;
void dfs(int node,int ata) {
// cerr << "node is : " << node <<'\n';
// for(auto x:s) cerr << x.st << ' ' << x.nd << '\n';
vector<int> roll;
// cerr << "roll upto : " << 2*der[node]-mxd[node][0] << "\n";
// cerr << node << " " << sz << '\n';
del(roll,2*der[node]-mxd[node][1]);
// cerr << node << " " << sz <<'\n';
add(node);
// cerr << node << " " << deep[node] << '\n';
for(int i:v[node]) {
if(i!=deep[node]) continue ;
dfs(i,node);
}
del(temp,der[node]);
// cerr << node << " " << sz << '\n';
del(roll,2*der[node]-mxd[node][0]);
// cerr << node << " " << sz <<'\n';
add(node);
for(int i:v[node]) {
if(i==ata || i==deep[node]) continue ;
dfs(i,node);
}
del(temp,der[node]);
umax(ans[node],cntd);
//rollback(roll);
}
void dfs1(int node,int ata) {
der[node]=der[ata]+1;
mxd[node][0]=mxd[node][1]=der[node];
deep[node]=node;
for(int i:v[node]) {
if(i==ata) continue ;
dfs1(i,node);
upd(node,mxd[i][0]);
if(mxd[node][0]==mxd[i][0]) {
deep[node]=i;
}
}
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<n;i++) {
int x,y;
scanf("%d %d",&x,&y);
v[x].pb(y);
v[y].pb(x);
}
for(int i=1;i<=n;i++) scanf("%d",c+i);
dia.find();
// cerr << "root is : " << dia.l << '\n';
dfs1(dia.l,0);
dfs(dia.l,0);
// cerr << "root is : " << dia.r << '\n';
dfs1(dia.r,0);
dfs(dia.r,0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
// cerr << tot_op << '\n';
}
Compilation message
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:211:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:217:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:224:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%d",c+i);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4988 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
15352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
320 ms |
19764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4988 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
