#include<bits/stdc++.h>
using namespace std;
const int N=2e5+2;
const int LOG=19;
int ar[N];
int ans[N][2],pts[2],level[N][2],ancestor[N][LOG][2],cnt=0;
bool used[N][2];
//int pos[N];
//set<int> color[N];
set<int> color;
vector<int> lis[N],adj[N];
void dfs(int x,int p){
if(cnt<2){
if(level[x][0]>=level[pts[cnt]][0]){
pts[cnt]=x;
}
}
lis[level[x][0]].push_back(x);
for(int i=0;i<adj[x].size();i++){
if(adj[x][i]!=p){
level[adj[x][i]][0]=level[x][0]+1;
dfs(adj[x][i],x);
}
}
}
void dfs1(int x,int p){ //right now cnt is above
int idx=0,i;
for(i=1;i<LOG;i++){
ancestor[x][i][cnt]=ancestor[ancestor[x][i-1][cnt]][i-1][cnt];
}
for(i=0;i<adj[x].size();i++){
if(adj[x][i]!=p){
level[adj[x][i]][cnt]=level[x][cnt]+1;
ancestor[adj[x][i]][0][cnt]=x;
dfs1(adj[x][i],x);
// if(color[pos[adj[x][i]]].size()>color[idx].size()){
// idx=pos[adj[x][i]];
// }
}
}
// pos[x]=idx;
// for(i=0;i<adj[x].size();i++){
// if(adj[x][i]!=p&&pos[adj[x][i]]!=idx){
// for(auto ite=color[pos[adj[x][i]]].begin();ite!=color[pos[adj[x][i]]].end();ite++){
// color[pos[x]].insert(*ite);
// }
// }
// }
// ans[x][cnt]=color[pos[x]].size();
// if(used[x][cnt]){
// color[pos[x]].insert(ar[x]);
// }
}
int findd(int x,int k,int idx){
while(k){
int y=__lg(k);
x=ancestor[x][y][idx];
k-=(1<<y);
}
return x;
}
int LCA(int x,int y,int idx){
if(level[x][idx]>level[y][idx]){
x=findd(x,level[x][idx]-level[y][idx],idx);
}
y=findd(y,level[y][idx]-level[x][idx],idx);
if(x==y){
return x;
}
for(int i=LOG-1;i>=0;i--){
if(ancestor[x][i][idx]!=ancestor[y][i][idx]){
x=ancestor[x][i][idx],y=ancestor[y][i][idx];
}
}
return ancestor[x][0][idx];
}
int dis(int x,int y){
return level[x][0]+level[y][0]-2*level[LCA(x,y,0)][0];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,i,j,k,l;
cin>>n>>m;
for(i=1;i<n;i++){
cin>>j>>k;
adj[j].push_back(k);
adj[k].push_back(j);
}
for(i=1;i<=n;i++){
cin>>ar[i];
}
dfs(1,1);
cnt++;
level[pts[0]][0]=0;
for(i=0;i<n;i++){
lis[i].clear();
}
//this maybe confusing ofter, but... it's ok because level using dfs is 0
dfs(pts[0],pts[0]);
for(i=0;i<n;i++){
if(lis[i].size()==1){
used[lis[i][0]][0]=true;
// cout<<lis[i][0]<<' ';
}
lis[i].clear();
}
// cout<<endl;
level[pts[1]][0]=0;
cnt++;
dfs(pts[1],pts[1]);
for(i=0;i<n;i++){
if(lis[i].size()==1){
used[lis[i][0]][1]=true;
}
lis[i].clear();
}
level[pts[0]][0]=0;
cnt=0;
dfs1(pts[0],pts[0]);
j=pts[1];
while(j){
ans[j][0]=color.size();
if(used[j][0]){
color.insert(ar[j]);
}
j=ancestor[j][0][0];
}
// for(i=1;i<=n;i++){
// cout<<ans[i][cnt]<<' ';
// }
// cout<<endl;
cnt++;
// for(i=0;i<n;i++){
// color[i].clear();
// }
level[pts[1]][1]=0;
dfs1(pts[1],pts[1]);
color.clear();
j=pts[0];
while(j){
ans[j][1]=color.size();
if(used[j][1]){
color.insert(ar[j]);
}
j=ancestor[j][0][1];
}
// for(i=1;i<=n;i++){
// cout<<ans[i][cnt]<<' ';
// }
// cout<<endl;
// cout<<dis(1,5)<<endl;
for(i=1;i<=n;i++){
j=dis(i,pts[0]);
k=dis(i,pts[1]);
if(j==k){
cout<<0<<'\n';
continue;
}
if(j<k){
// cout<<findd(pts[1],k-j,0)<<" cac\n";
cout<<ans[findd(pts[1],k-j,0)][0]<<'\n';
}
else{
// cout<<findd(pts[0],j-k,1)<<" cac\n";
cout<<ans[findd(pts[0],j-k,1)][1]<<'\n';
}
}
}
Compilation message
joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void dfs1(int, int)':
joi2019_ho_t5.cpp:31:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:27:6: warning: unused variable 'idx' [-Wunused-variable]
int idx=0,i;
^~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:83:16: warning: unused variable 'l' [-Wunused-variable]
int n,m,i,j,k,l;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
10232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
281 ms |
36004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
399 ms |
46328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
10232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
