#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;
int n, m, k, u, v, x, y, t, a, b;
int C[MAXN], par[MAXN], h[MAXN], ans[MAXN];
pii D[MAXN];
pii seg[MAXN<<2];
int lazy[MAXN<<2];
vector<int> G[MAXN];
inline void add_lazy(int id, int val){
seg[id].first+=val;
lazy[id]+=val;
}
inline void shift(int id){
if (!lazy[id]) return ;
add_lazy(id<<1, lazy[id]);
add_lazy(id<<1 | 1, lazy[id]);
lazy[id]=0;
}
inline pii Merge(pii x, pii y){
return (x.first==y.first?pii(x.first, x.second+y.second):min(x, y));
}
pii Build(int id, int tl, int tr){
lazy[id]=0;
if (tr-tl==1) return seg[id]={0, 1};
int mid=(tl+tr)>>1;
return seg[id]=Merge(Build(id<<1, tl, mid), Build(id<<1 | 1, mid, tr));
}
void Add(int id, int tl, int tr, int l, int r, int val){
if (r<=tl || tr<=l) return ;
if (l<=tl && tr<=r){
add_lazy(id, val);
return ;
}
shift(id);
int mid=(tl+tr)>>1;
Add(id<<1, tl, mid, l, r, val);
Add(id<<1 | 1, mid, tr, l, r, val);
seg[id]=Merge(seg[id<<1], seg[id<<1 | 1]);
}
pii Get(int id, int tl, int tr, int l, int r){
if (r<=tl || tr<=l) return seg[0];
if (l<=tl && tr<=r) return seg[id];
shift(id);
int mid=(tl+tr)>>1;
return Merge(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}
void dfs1(int node, int p){
par[node]=p;
h[node]=h[p]+1;
D[node]={0, node};
for (int v:G[node]) if (v!=p){
dfs1(v, node);
D[node]=max(D[node], {D[v].first+1, D[v].second});
}
}
void dfs2(int node){
pii p=Get(1, 1, n+1, 1, h[node]-D[node].first);
if (!p.first) ans[node]=max(ans[node], p.second);
for (int v:G[node]) if (v!=par[node]) Add(1, 1, n+1, h[node]-D[v].first-1, h[v], +1);
for (int v:G[node]) if (v!=par[node]){
Add(1, 1, n+1, h[node]-D[v].first-1, h[v], -1);
dfs2(v);
Add(1, 1, n+1, h[node]-D[v].first-1, h[v], +1);
}
for (int v:G[node]) if (v!=par[node]) Add(1, 1, n+1, h[node]-D[v].first-1, h[v], -1);
}
void Solve(int root){
dfs1(root, 0);
Build(1, 1, n+1);
dfs2(root);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>m;
for (int i=1; i<n; i++){
cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
}
for (int i=1; i<=n; i++) cin>>C[i];
dfs1(1, 0);
int root=D[1].second;
Solve(root);
dfs1(root, 0); // pashm
root=D[root].second;
Solve(root);
for (int i=1; i<=n; i++) cout<<min(ans[i], m)<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
5228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
643 ms |
16472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
936 ms |
23276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
5228 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
