1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #pragma GCC optimize(3,"Ofast","inline")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
#define int long long
#define endl '\n'
int cnt,head[N];
int depth[N];
int fa[N][20];
int q[N],n;
int dp[2*N];
vector<int>s[N*2];
struct edge
{
int nx;
int to;
};
edge ed[2*N];
void add(int a,int b)
{
ed[++cnt].nx=head[a];
ed[cnt].to=b;
head[a]=cnt;
}
void bfs(int root)
{ memset(depth,0x3f,sizeof(depth));
depth[0]=0;depth[root]=1;
queue<int>q;
q.push(root);
while(q.size())
{
int t=q.front();
q.pop();
for(int i=head[t];i!=-1;i=ed[i].nx)
{
int j=ed[i].to;
if(depth[j]>depth[t]+1)
{
depth[j]=depth[t]+1;
q.push(j);
fa[j][0]=t;
for(int k=1;k<=18;k++)
{
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
return;
}
int lca(int x,int y)
{
if (depth[x] < depth[y]) {
swap(x, y);
}
for (int i = 19; i >= 0; i--) {
if(depth[x] - depth[y] >= (1 << i)) {
x=fa[x][i];
}
}
if (x == y) {
return x;
}
for (int i = 19; i >= 0; i--) {
if(fa[x][i] != fa[y][i]) {
x = fa[x][i], y = fa[y][i];
}
}
return fa[x][0];
}
signed main()
{
cin>>n;
int root=0,to;
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++)
{
int a,b; cin>>a>>b;
add(a,b),add(b,a);
}
cin>>root>>to;
bfs(root);
for(int i=1;i<=n;i++){
s[depth[i]-1].push_back(i);
}
for(int i=1;i<=n+n;i++){
dp[i]=dp[i-1];
int sum=0;
if(s[i].size()) {
int u=s[i][0];
for(int j=1;j<s[i].size();j++){
int v=s[i][j];
int m=lca(u,v);
m=depth[u]+depth[v]-2*depth[m];
sum=max(sum,m);
}
dp[i]=max(dp[i]+1,sum);
}
}
for(int i=1;i<=n;i++){
int l=1,r=n;
while(l<r){
int mid=(l+r)/2;
int len=dp[to+mid];
len=(len+1)/2;
if(len<=(int)i*mid) r=mid;
else l=mid+1;
}
cout<<to+l<<" ";
}
return 0;
}
|
