This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
/**
* Author: Lucian Bicsi
* Date: 2017-10-31
* License: CC0
* Source: folklore
* Description: Zero-indexed max-tree. Bounds are inclusive to the left and exclusive to the right. Can be changed by modifying T, f and unit.
* Time: O(\log N)
* Status: stress-tested
*/
struct Tree {
typedef int T;
static constexpr T unit = INT_MIN;
T f(T a, T b) { return max(a, b); } // (any associative fn)
vector<T> s; int n;
Tree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, T val) {
pos--;
pos += n;
s[pos] = f(s[pos], val);
for (; pos >>= 1;) // do u mean += val???
s[pos] = f(s[pos << 1], s[pos << 1 | 1]);
}
T query(int b, int e) { // query [b, e)
b--;
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b >>= 1, e >>= 1) {
if (b & 1) ra = f(ra, s[b++]);
if (e & 1) rb = f(s[--e], rb);
}
return f(ra, rb);
}
void reset(int pos) {
pos--;
pos += n;
s[pos] = unit;
for (; pos >>= 1;) // do u mean += val???
s[pos] = f(s[pos << 1], s[pos << 1 | 1]);
}
} tr;
const int N = 2e5 + 5;
const int lg = 18;
using tri = array<int, 3>; // index, length, size
vector<ii> upds;
int n;
int sub[N], in[N], tym = 0, lvl[N], dp[lg][N];
vi g[N];
int sub0[N];
int vis[N]; // already centroid
bool isanc(int u, int v) { // is u v's anc?
return in[u] <= in[v] and in[v] < in[u]+sub[u];
}
int __lca(int u, int v) {
if(lvl[u] > lvl[v]) swap(u, v);
int d = lvl[v] - lvl[u];
for(int i = 0; i < lg; ++i)
if(d >> i & 1) v = dp[i][v];
if(u == v) return u;
for(int i = lg-1; i >= 0; --i)
if(dp[i][u] != dp[i][v])
u = dp[i][u], v = dp[i][v];
return dp[0][u];
}
int kth_anc(int u, int k) {
for(int i = 0; i < lg; ++i)
if(k >> i & 1) u = dp[i][u];
return u;
}
int dis(int u, int v) {
return lvl[u] + lvl[v] - 2*lvl[__lca(u,v)];
}
int directed_size(int u, int v) { // it MUST be and EDGE
return in[u] < in[v] ? sub0[v] : n - sub0[u];
}
void dfs_sizes(int u, int dad) {
sub[u] = 1;
for(int v : g[u]) if(!vis[v] and v != dad) {
dfs_sizes(v, u);
sub[u] += sub[v];
}
}
int centroid(int u, int dad, int thr) {
for(int v : g[u]) if(!vis[v] and v != dad and sub[v] > thr) {
return centroid(v, u, thr);
} return u;
}
void dfs_calc(int u, int dad, int level, vector<ii>& bag) {
bag.emplace_back(level, directed_size(dad, u));
for(int v : g[u]) if(!vis[v] and v != dad) {
dfs_calc(v, u, level+1, bag);
}
}
int decompose(int u) {
dfs_sizes(u, -1);
int cen = centroid(u, -1, sub[u]/2);
vi back;
vector<vector<ii>> bags;
for(int v : g[cen]) if(!vis[v]) {
back.emplace_back(directed_size(v, cen));
bags.push_back({});
dfs_calc(v, cen, 1, bags.back());
}
for(int i = 0; i < sz(back); ++i) {
for(auto& [len, size] : bags[i]) {
int mx = tr.query(size, n);
if(mx != INT_MIN) {
upds.emplace_back(mx + len + 1, size);
}
}
for(auto& [len, size] : bags[i]) {
tr.update(size, len);
}
}
for(int i = 0; i < sz(back); ++i) {
for(auto& [len, size] : bags[i]) {
tr.reset(size);
}
}
for(int i = sz(back)-1; i >= 0; --i) {
for(auto& [len, size] : bags[i]) {
int mx = tr.query(size, n);
if(mx != INT_MIN) {
upds.emplace_back(mx + len + 1, size);
}
}
for(auto& [len, size] : bags[i]) {
tr.update(size, len);
}
}
for(int i = 0; i < sz(back); ++i) {
for(auto& [len, size] : bags[i]) {
tr.reset(size);
}
}
for(int i = 0; i < sz(back); ++i) {
for(auto& [len, size] : bags[i]) {
upds.emplace_back(len+1, min(size, back[i]));
}
}
vis[cen] = 1;
for(int v : g[cen]) if(!vis[v]) {
decompose(v);
}
return cen;
}
void dfs_initial(int u, int dad) {
in[u] = ++tym;
sub0[u] = 1;
lvl[u] = dad ? lvl[dad] + 1 : 0;
dp[0][u] = dad;
for(int i = 1; i < lg; ++i)
dp[i][u] = dp[i-1][dp[i-1][u]];
for(int v : g[u]) if(v != dad) {
dfs_initial(v, u);
sub0[u] += sub0[v];
}
}
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
upds.reserve(3*lg*N);
scanf("%d", &n);
tr = Tree(n);
// assert(n <= 4000);
for(int i = 1; i < n; ++i) {
int u, v; scanf("%d %d", &u, &v);
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs_initial(1, 0);
decompose(1);
vi ans(n+1, 1);
sort(all(upds)); reverse(all(upds));
int ptr = 0;
for(auto [d, mn] : upds) {
while(ptr < mn) {
ans[2*(++ptr)] = d;
}
}
for(int i = 1; i <= n; ++i)
printf("%d\n", ans[i]);
return 0;
}
Compilation message (stderr)
meetings2.cpp: In function 'int main(int, const char**)':
meetings2.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
185 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
meetings2.cpp:189:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
189 | int u, v; scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |