제출 #895903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895903		NeroZein	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1042 ms	31504 KiB

meetings2

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;

int n;
int sz[N];
int ans[N];
bool blocked[N];
vector<int> g[N];

void find_sizes(int v, int p) {
  sz[v] = 1; 
  for (int u : g[v]) {
    if (!blocked[u] && u != p) {
      find_sizes(u, v); 
      sz[v] += sz[u];
    }
  }
}

int find_centroid(int v, int p, int x) {
  for (int u : g[v]) {
    if (!blocked[u] && u != p && sz[u] > x / 2) {
      return find_centroid(u, v, x); 
    }
  }
  return v; 
}

void dfs(int v, int p, int dep, vector<pair<int, int>>& vec) {
  vec.emplace_back(sz[v], dep);
  for (int u : g[v]) {
    if (!blocked[u] && u != p) {
      dfs(u, v, dep + 1, vec); 
    }
  }
}

void merge(set<pair<int, int>>& se, vector<pair<int, int>>& vec) {
  for (auto [sub, dep] : vec) {
    auto it = se.lower_bound(make_pair(sub, -1));
    if (it == se.end()) {
      se.emplace(sub, dep);
    } else {
      if (it->second >= dep) {
        continue; 
      }
      it = se.insert({sub, dep}).first; 
      vector<pair<int, int>> to_erase; 
      while (it != se.begin()) {
        it = prev(it);
        if (it->second < dep) {
          to_erase.push_back(*it); 
        } else {
          break;
        }
      }
      for (auto p : to_erase) {
        se.erase(p);
      }
    }
  }
}

void decompose(int v) {
  find_sizes(v, v); 
  int centroid = find_centroid(v, v, sz[v]); 
  find_sizes(centroid, centroid); 
  blocked[centroid] = true; 
  for (int rep = 0; rep < 2; ++rep) {
    set<pair<int, int>> se; 
    for (int u : g[centroid]) {
      if (blocked[u]) {
        continue;
      }
      vector<pair<int, int>> vec; 
      dfs(u, u, 1, vec); 
      for (int i = 0; i < (int) vec.size(); ++i) {
        auto [sub, dep] = vec[i];
        auto it = se.lower_bound(make_pair(sub, -1));
        if (it != se.end()) {
          ans[sub] = max(ans[sub], dep + it->second); 
        }
        //if (sub < sz[centroid] - sub) {//always true
          ans[sub] = max(ans[sub], dep);
        //}
      }      
      merge(se, vec); 
    }
    reverse(g[centroid].begin(), g[centroid].end()); 
  }
  for (int u : g[centroid]) {
    if (!blocked[u]) {
      decompose(u); 
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  decompose(1);
  for (int i = n; i >= 1; --i) {
    ans[i] = max(ans[i], ans[i + 1]); 
  }
  for (int i = 1; i <= n; ++i) {
    cout << (i % 2 ? 1 : ans[i / 2] + 1) << '\n';
  }
  return 0;
}

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