#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>;
long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200006)
int n, p[MAXN][18], dist[MAXN], st[MAXN], en[MAXN], co, sz[MAXN];
vector<int> v[MAXN];
void dfs(int x,int par) {
st[x] = co++, p[x][0]=par, sz[x] = 1;
for(auto i:v[x]) if(i^par) dist[i]=dist[x]+1, dfs(i, x), sz[x] += sz[i];
en[x] = co-1;
}
bool isp(int a,int b) { return st[a]<=st[b]&&en[a]>=en[b]; }
int lca(int x,int y) {
if(isp(x,y)) return x;
if(isp(y,x)) return y;
DEC(i,17,0) if(!isp(p[x][i], y)) x=p[x][i];
return p[x][0];
}
int disty(int a,int b) { return dist[a]+dist[b]-2*dist[lca(a,b)]; }
int A, B, out[MAXN];
int main() {
FAST
cin>>n;
FOR(i,1,n-1) {
int a, b;
cin>>a>>b;
v[a].eb(b), v[b].eb(a);
}
dfs(1, 1);
FOR(i,1,n) if(sz[i] > n/2) {
for(auto j:v[i]) if(j^p[i][0]) if(n - sz[j] <= n/2) { sz[i] = n - sz[j]; break; }
// if(sz[i] > n/2)
}
FOR(j,1,17) FOR(i,1,n) p[i][j]=p[p[i][j-1]][j-1];
A=B=-1;
vector<pi> V;
FOR(i,1,n) {
// cerr<<i<<": "<<sz[i]<<'\n';
V.eb(sz[i], i);
}
sort(all(V));
for(ll i=n/2;i>=1;--i) {
while(V.size() && V.back().f >= i) {
int x = V.back().s; V.pop_back();
if(A==-1) A=B=x;
else {
if(disty(x, A) >= disty(A, B) && disty(x, A) >= disty(x, B)) {
B = x;
} else if(disty(x, B) >= disty(A, B)) {
A = x;
}
}
}
if(A == -1) out[i*2]=0;
else out[i*2] = disty(A, B);
}
FOR(i,1,n) cout<<out[i]+1<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
5032 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
5032 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
4940 KB |
Output is correct |
10 |
Correct |
4 ms |
5028 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
5032 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
5032 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
4940 KB |
Output is correct |
10 |
Correct |
4 ms |
5028 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
5032 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
5032 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
4940 KB |
Output is correct |
10 |
Correct |
4 ms |
5028 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |