#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct seg
{
int c[800010],sm[800010],t[800010];
seg()
{
fill(c,c+800010,0);
fill(sm,sm+800010,0);
fill(t,t+800010,0);
}
inline void set(int n)
{
t[n]=c[n]>0?sm[n]:(n<400005?t[n*2]+t[n*2+1]:0);
return;
}
void set(int n,int s,int e,int x,int p)
{
if(s==e)
{
sm[n]=p;
set(n);
return;
}
int m=(s+e)/2;
if(x>m)
set(n*2+1,m+1,e,x,p);
else
set(n*2,s,m,x,p);
sm[n]=sm[n*2]+sm[n*2+1];
set(n);
return;
}
bool get(int n,int s,int e,int x)
{
if(c[n]>0)
return 1;
if(s==e)
return 0;
int m=(s+e)/2;
if(x>m)
return get(n*2+1,m+1,e,x);
return get(n*2,s,m,x);
}
void si(int n,int s,int e,int S,int E,int p)
{
if(s>E||S>e)
return;
if(S<=s&&e<=E)
{
c[n]+=p;
set(n);
return;
}
int m=(s+e)/2;
si(n*2,s,m,S,E,p);
si(n*2+1,m+1,e,S,E,p);
set(n);
return;
}
inline int sq()
{
return t[1];
}
}st;
vector<int>adj[200010];
int dp[200010],dp2[200010];
int fd[200010],sd[200010];
bool ch[200010];
int pos[200010];
int n,m;
void dfs(int x,int p)
{
ch[x]=dp[p]+1>dp[x];
dp[x]=dp[p]+1;
for(int&t:adj[x])
if(t!=p)
dfs(t,x);
fd[x]=sd[x]=0;
dp2[x]=1;
for(int&t:adj[x])
{
if(t==p)
continue;
dp2[x]=max(dp2[x],dp2[t]+1);
if(fd[x]<dp2[t])
sd[x]=fd[x],fd[x]=dp2[t];
else if(sd[x]<dp2[t])
sd[x]=dp2[t];
}
return;
}
int ans[200010],c[200010];
int c2;
void dfs2(int x,int p)
{
if(ch[x])
{
int up=max(1,dp[x]-fd[x]);
if(up<dp[x])
st.si(1,1,n,up,dp[x]-1,1);
ans[x]=c2-st.sq();
if(up<dp[x])
st.si(1,1,n,up,dp[x]-1,-1);
}
int pp=pos[c[x]];
bool cn=0;
if(pp==0||st.get(1,1,n,pp))
pos[c[x]]=dp[x],cn=1,st.set(1,1,n,dp[x],1),c2++;
for(int&t:adj[x])
{
if(t==p)
continue;
int up=max(1,dp[x]-(dp2[t]==fd[x]?sd[x]:fd[x]));
if(up<dp[x])
st.si(1,1,n,up,dp[x]-1,1);
dfs2(t,x);
if(up<dp[x])
st.si(1,1,n,up,dp[x]-1,-1);
}
if(cn)
pos[c[x]]=pp,st.set(1,1,n,dp[x],0),c2--;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
adj[u].eb(v);
adj[v].eb(u);
}
for(int i=0;i++<n;)
cin>>c[i];
dfs(1,0);
int l1=max_element(dp+1,dp+n+1)-dp;
dfs(l1,0);
int l2=max_element(dp+1,dp+n+1)-dp;
for(int i=0;i++<n;)
ch[i]=0,dp[i]=dp2[i]=0;
dfs(l1,0);
dfs2(l1,0);
for(int i=0;i++<n;)
ch[i]=0;
dfs(l2,0);
dfs2(l2,0);
for(int i=0;i++<n;)
cout<<ans[i]<<'\n';
cout.flush();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
14584 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
421 ms |
21172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
652 ms |
24404 KB |
Output is correct |
| 2 |
Correct |
1002 ms |
48032 KB |
Output is correct |
| 3 |
Correct |
99 ms |
18296 KB |
Output is correct |
| 4 |
Correct |
903 ms |
26924 KB |
Output is correct |
| 5 |
Correct |
1072 ms |
49704 KB |
Output is correct |
| 6 |
Correct |
1000 ms |
38160 KB |
Output is correct |
| 7 |
Correct |
871 ms |
27008 KB |
Output is correct |
| 8 |
Correct |
941 ms |
31572 KB |
Output is correct |
| 9 |
Correct |
1004 ms |
29944 KB |
Output is correct |
| 10 |
Correct |
836 ms |
29432 KB |
Output is correct |
| 11 |
Execution timed out |
47 ms |
18552 KB |
Time limit exceeded (wall clock) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
14584 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
