Submission #593180

#	Time	Username	Problem	Language	Result	Execution time	Memory
593180		SuffixAutomata	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	370 ms	45772 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll
const int MOD = 1000000007;

vector<int> elist[200005];

int fa[200005], sz[200005], dep[200005], mxs[200005];

int dfss(int u, int f) {
  fa[u] = f, sz[u] = 1;
  dep[u] = dep[f] + 1;
  for (int v : elist[u])
    if (v != f)
      sz[u] += dfss(v, u), mxs[u] = max(mxs[u], sz[v]);
  return sz[u];
}

int ans[100005];

int fa2[200005][20];
int be[200005], en[200005], clo;

void dfs3(int u, int f) {
  fa2[u][0] = f;
  for (int i = 1; i < 20; i++)
    fa2[u][i] = fa2[fa2[u][i - 1]][i - 1];
  be[u] = clo++;
  for (int v : elist[u])
    if (v != f)
      dfs3(v, u);
  en[u] = clo;
}

int lca(int u, int v) {
  if (be[u] <= be[v] && be[v] < en[u])
    return u;
  for (int i = 19; i >= 0; i--) {
    int x = fa2[u][i];
    if (!(be[x] <= be[v] && be[v] < en[x]))
      u = x;
  }
  return fa[u];
}

int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    int a, b;
    cin >> a >> b;
    elist[a].pb(b);
    elist[b].pb(a);
  }
  if (n == 1) {
    cout << "1\n";
    return 0;
  }
  if (n == 2) {
    cout << "1\n2\n";
    return 0;
  }
  dfss(1, 0);
  int rt = 1, rtv = mxs[1];
  for (int i = 1; i <= n; i++)
    if (max(mxs[i], n - sz[i]) < rtv) {
      rtv = max(mxs[i], n - sz[i]);
      rt = i;
    }
  dfss(rt, 0);
  dfs3(rt, 0);
  en[0] = 1e9;
  vector<pii> ps;
  for (int i = 1; i <= n; i++)
    if (i != rt) {
      ps.pb({sz[i], i});
      assert(sz[i] <= n / 2);
    }
  sort(all(ps));
  int u = rt, v = rt, ca = 0;
  for (int i = n / 2; i >= 1; i--) {
    while (ps.size() && ps.back().fi >= i) {
      int d;
      d = dis(u, ps.back().se);
      if (d > ca)
        v = ps.back().se, ca = d;
      d = dis(ps.back().se, v);
      if (d > ca)
        u = ps.back().se, ca = d;
      ps.pop_back();
    }
    ans[i] = ca + 1;
  }
  for (int i = n / 2; i >= 1; i--)
    ans[i] = max(ans[i], ans[i + 1]);
  for (int i = 1; i <= n; i++) {
    if (i % 2)
      cout << "1\n";
    else
      cout << ans[i / 2] << "\n";
  }
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80