#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 200000
int N, M;
int A[MAXN], B[MAXN], C[MAXN];
vector<int> e[MAXN];
int dep[MAXN], mxdep[MAXN][2];
int seg[MAXN*4], cnt[MAXN*4];
int ans[MAXN];
void mkseg(int idx, int l, int r){
seg[idx]=0;
cnt[idx]=r-l+1;
if(l<r){
int m=(l+r)/2;
mkseg(idx*2, l, m);
mkseg(idx*2+1, m+1, r);
}
}
void updseg(int idx, int l, int r, int x, int y, int z){
//if(idx==1) printf("updseg(%d %d %d)\n", x, y, z);
if(x>y) return;
if(x<=l&&r<=y) seg[idx]+=z;
else if(l<=y&&x<=r){
int m=(l+r)/2;
updseg(idx*2, l, m, x, y, z);
updseg(idx*2+1, m+1, r, x, y, z);
if(seg[idx*2]<seg[idx*2+1]){
seg[idx]=seg[idx*2];
cnt[idx]=cnt[idx*2];
}
else if(seg[idx*2]==seg[idx*2+1]){
seg[idx]=seg[idx*2];
cnt[idx]=cnt[idx*2]+cnt[idx*2+1];
}
else{
seg[idx]=seg[idx*2+1];
cnt[idx]=cnt[idx*2+1];
}
}
}
int gseg(int idx, int l, int r, int x, int y){
if(seg[idx]>0) return 0;
if(x<=l&&r<=y) return cnt[idx];
if(r<x||y<l) return 0;
int m=(l+r)/2;
return gseg(idx*2, l, m, x, y)+gseg(idx*2+1, m+1, r, x, y);
}
void dfs1(int x){
mxdep[x][0]=dep[x];
mxdep[x][1]=0;
for(auto a:e[x]) if(dep[a]==-1){
dep[a]=dep[x]+1;
dfs1(a);
if(mxdep[a][0]>mxdep[x][1]) mxdep[x][1]=mxdep[a][0];
if(mxdep[x][1]>mxdep[x][0]) swap(mxdep[x][0], mxdep[x][1]);
}
}
void dfs2(int x){
//printf("dfs2(%d)\n", x);
updseg(1, 0, N-1, max(0, 2*dep[x]-mxdep[x][0]), dep[x]-1, 1);
ans[x]=max(ans[x], gseg(1, 0, N-1, 0, dep[x]));
if(e[x].size()-(dep[x]==0?0:1)>1){
//printf("x=%d\n", x);
for(auto a:e[x]) if(dep[a]>dep[x]&&mxdep[a][0]!=mxdep[x][0]) dfs2(a);
//printf("x=%d*\n", x);
updseg(1, 0, N-1, max(0, 2*dep[x]-mxdep[x][0]), dep[x]-1, -1);
updseg(1, 0, N-1, 2*dep[x]-mxdep[x][1], dep[x]-1, 1);
for(auto a:e[x]) if(dep[a]>dep[x]&&mxdep[a][0]==mxdep[x][0]) dfs2(a);
updseg(1, 0, N-1, 2*dep[x]-mxdep[x][1], dep[x]-1, -1);
}
else{
updseg(1, 0, N-1, max(0, 2*dep[x]-mxdep[x][0]), dep[x]-1, -1);
for(auto a:e[x]) if(dep[a]>dep[x]) dfs2(a);
}
}
int main(){
int X, Y;
scanf("%d%d", &N, &M);
for(int i=0; i<N-1; i++) scanf("%d%d", A+i, B+i);
for(int i=1; i<=N; i++) scanf("%d", C+i);
for(int i=0; i<N-1; i++){
e[A[i]].push_back(B[i]);
e[B[i]].push_back(A[i]);
}
for(int i=1; i<=N; i++) dep[i]=-1;
dep[1]=0;
dfs1(1);
X=1;
for(int i=1; i<=N; i++) if(dep[i]>dep[X]) X=i;
for(int i=1; i<=N; i++) dep[i]=-1;
dep[X]=0;
mkseg(1, 0, N-1);
dfs1(X);
//for(int i=1; i<=N; i++) printf("(%d %d %d)\n", dep[i], mxdep[i][0], mxdep[i][1]);
//printf("[%d]\n", X);
dfs2(X);
Y=1;
for(int i=1; i<=N; i++) if(dep[i]>dep[Y]) Y=i;
for(int i=1; i<=N; i++) dep[i]=-1;
dep[Y]=0;
dfs1(Y);
mkseg(1, 0, N-1);
dfs2(Y);
for(int i=1; i<=N; i++) printf("%d\n", ans[i]-1);
return 0;
}
Compilation message
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:90: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:91:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<N-1; i++) scanf("%d%d", A+i, B+i);
~~~~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:92:31: 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);
~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
5248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
321 ms |
15864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
513 ms |
20948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
5248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
