Submission #593153

#	Time	Username	Problem	Language	Result	Execution time	Memory
593153		SuffixAutomata	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	5028 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];
pii mxs[200005];

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

int ans[100005];

int sub[200005];

void dfs2(int u, int f, int x) {
  dep[u] = dep[f] + 1;
  sub[u] = x;
  for (int v : elist[u])
    if (v != f)
      dfs2(v, u, x);
}

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 << endl;
    return 0;
  }
  dfss(1, 0);
  int rt = 1;
  while (mxs[rt].fi > n / 2)
    rt = mxs[rt].se;
  dfss(rt, 0);
  for (int i : elist[rt])
    dfs2(i, rt, i);
  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));
  vector<int> active(n + 1), mdp(n + 1);
  multiset<int> mdp2;
  mdp2.insert(0);
  for (int i : elist[rt])
    mdp2.insert(mdp[i]);
  for (int i = n; i >= 1; i--) {
    while (ps.size() && ps.back().fi >= i) {
      int u = sub[ps.back().se];
      mdp2.erase(mdp2.find(mdp[u]));
      mdp[u] = max(mdp[u], dep[ps.back().se]);
      mdp2.insert(mdp[u]);
      ps.pop_back();
    }
    if (i <= n / 2)
      ans[i] = *mdp2.rbegin() + *next(mdp2.rbegin()) + 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: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80