#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7;
vector<int>V[LIM];
int T[LIM], ile[LIM], wynik[LIM], odl[2][LIM], odw[LIM], wys[LIM], jaki[LIM], aktile;
int trma[4*LIM], trmi[4*LIM], lazy[4*LIM], N=1;
vector<int>ojcowie;
void spl(int v) {
trma[2*v]+=lazy[v];
trma[2*v+1]+=lazy[v];
trmi[2*v]+=lazy[v];
trmi[2*v+1]+=lazy[v];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
if(r<a || b<l) return;
if(a<=l && r<=b) {
trma[v]+=x;
trmi[v]+=x;
lazy[v]+=x;
return;
}
if(lazy[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b, x);
upd(2*v+1, mid+1, r, a, b, x);
trma[v]=max(trma[2*v], trma[2*v+1]);
trmi[v]=min(trmi[2*v], trmi[2*v+1]);
}
int zejdzmi(int v, int l, int r) {
if(l==r) return l;
if(lazy[v]) spl(v);
int mid=(l+r)/2;
if(trmi[2*v]<=trmi[2*v+1]) return zejdzmi(2*v, l, mid);
return zejdzmi(2*v+1, mid+1, r);
}
int zejdzma(int v, int l, int r) {
if(l==r) return l;
if(lazy[v]) spl(v);
int mid=(l+r)/2;
if(trma[2*v]>=trma[2*v+1]) return zejdzma(2*v, l, mid);
return zejdzma(2*v+1, mid+1, r);
}
void dodaj(int x) {
if(odw[x]) return;
odw[x]=1;
++ile[T[x]];
if(ile[T[x]]==1) ++aktile;
}
void usun(int x) {
if(!odw[x]) return;
odw[x]=0;
--ile[T[x]];
if(ile[T[x]]==0) --aktile;
}
void schodz() {
while(trma[1]>0) {
int p=zejdzma(1, 0, N-1);
usun(ojcowie[p]);
upd(1, 0, N-1, p, p, -INF);
}
while(trmi[1]==-INF) {
int p=zejdzmi(1, 0, N-1);
dodaj(ojcowie[p]);
upd(1, 0, N-1, p, p, INF);
}
}
void DFS(int x, int o, int k) {
for(auto i : V[x]) if(i!=o) {
odl[k][i]=odl[k][x]+1;
DFS(i, x, k);
}
}
void DFS2(int x, int o) {
for(auto i : V[x]) if(i!=o) {
DFS2(i, x);
wys[x]=max(wys[x], wys[i]+1);
}
}
void DFS3(int x, int o, int k) {
ojcowie.pb(x);
upd(1, 0, N-1, odl[k][x]-wys[x], odl[k][x]-1, 1);
schodz();
if(jaki[x]==k) wynik[x]=aktile;
upd(1, 0, N-1, odl[k][x]-wys[x], odl[k][x]-1, -1);
dodaj(x);
pair<int,int>ma={-1, -1};
for(auto i : V[x]) if(i!=o) {
if(wys[i]>=ma.st) {
ma.nd=ma.st;
ma.st=wys[i];
} else ma.nd=max(ma.nd, wys[i]);
}
for(auto i : V[x]) if(i!=o) {
int p=ma.st;
if(wys[i]==p) p=ma.nd;
upd(1, 0, N-1, odl[k][x]-p-1, odl[k][x]-1, 1);
DFS3(i, x, k);
upd(1, 0, N-1, odl[k][x]-p-1, odl[k][x]-1, -1);
}
usun(x);
ojcowie.pop_back();
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
while(N<n) N*=2;
rep(i, n-1) {
int a, b;
cin >> a >> b; --a; --b;
V[a].pb(b);
V[b].pb(a);
}
rep(i, n) {
cin >> T[i]; --T[i];
}
DFS(0, 0, 0);
pair<int,int>ma={-1, -1};
rep(i, n) ma=max(ma, {odl[0][i], i});
int x=ma.nd;
odl[0][x]=0;
DFS(x, x, 0);
ma={-1, -1};
rep(i, n) ma=max(ma, {odl[0][i], i});
int y=ma.nd;
DFS(y, y, 1);
rep(i, n) if(odl[0][i]<odl[1][i]) jaki[i]=1;
rep(i, n) wys[i]=0;
DFS2(x, x);
DFS3(x, x, 0);
rep(i, n) wys[i]=0;
rep(i, 2*N) trma[i]=trmi[i]=lazy[i]=0;
rep(i, n) odw[i]=0;
rep(i, m) ile[i]=0;
aktile=0;
DFS2(y, y);
DFS3(y, y, 1);
rep(i, n) cout << wynik[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
234 ms |
18224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
352 ms |
23676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
