結果

問題 No.3405 Engineering University of Tree
コンテスト
ユーザー とりゐ
提出日時 2025-12-12 14:37:37
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 872 ms / 2,000 ms
コード長 6,056 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,997 ms
コンパイル使用メモリ 313,820 KB
実行使用メモリ 123,856 KB
最終ジャッジ日時 2025-12-12 14:38:00
合計ジャッジ時間 16,509 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define ll long long
#define elif else if
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int, int>

#define repname(a, b, c, d, e, ...) e
#define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x) for (int i = 0; i < (x); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c))

template <typename T>
ostream &operator<<(ostream &os, const set<T> s)
{
  os << "{";
  bool first = true;
  for (const auto &x : s)
  {
    if (!first)
      os << ", ";
    os << x;
    first = false;
  }
  os << "}";
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> s)
{
  os << "{";
  bool first = true;
  for (const auto &x : s)
  {
    if (!first)
      os << ", ";
    os << x;
    first = false;
  }
  os << "}";
  return os;
}

template <typename K, typename V>
ostream &operator<<(ostream &os, const map<K, V> m)
{
  os << "{";
  bool first = true;
  for (const auto &[key, value] : m)
  {
    if (!first)
      os << ", ";
    os << key << ": " << value;
    first = false;
  }
  os << "}";
  return os;
}

template <typename K, typename V>
ostream &operator<<(ostream &os, const unordered_map<K, V> m)
{
  os << "{";
  bool first = true;
  for (const auto &[key, value] : m)
  {
    if (!first)
      os << ", ";
    os << key << ": " << value;
    first = false;
  }
  os << "}";
  return os;
}

template <typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> a)
{
  os << "(";
  for (size_t i = 0; i < N; ++i)
  {
    if (i > 0)
      os << ", ";
    os << a[i];
  }
  os << ")";
  return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p)
{
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> v)
{
  os << "[";
  for (int i = 0; i < v.size(); ++i)
  {
    if (i > 0)
      os << ", ";
    os << v[i];
  }
  os << "]";
  return os;
}

template <class T>
void print(T x)
{
  cout << x << '\n';
}

template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail)
{
  cout << head << ' ';
  print(forward<Tail>(tail)...);
}

// -----------------------------------------------

struct LCA
{
  int n;
  vvi G, st;
  vi dep, S, FS;

  int LOG(int i) { return 31 - __builtin_clz(i); }

  LCA(int n, vvi &G, int root) : n(n), G(G), dep(n, -1), FS(n)
  {
    dep[root] = 0;
    dfs(root, -1);
    int L = S.size();
    st.resize(LOG(L) + 1);
    st[0] = S;
    int b = 1;
    rep(i, LOG(L))
    {
      int sz = st[i].size() - b;
      st[i + 1].resize(sz);
      rep(j, sz)
      {
        int u = st[i][j];
        int v = st[i][j + b];
        st[i + 1][j] = (dep[u] <= dep[v]) ? u : v;
      }
      b *= 2;
    }
  }

  void dfs(int v, int p)
  {
    FS[v] = S.size();
    S.push_back(v);
    for (auto u : G[v])
    {
      if (u != p)
      {
        dep[u] = dep[v] + 1;
        dfs(u, v);
        S.push_back(v);
      }
    }
  }

  int lca(int u, int v)
  {
    int x = FS[u], y = FS[v];
    if (x > y)
      swap(x, y);
    int l = LOG(y - x + 1);
    int px = st[l][x], py = st[l][y - (1 << l) + 1];
    return (dep[px] <= dep[py]) ? px : py;
  }
};

/*
- `AuxiliaryTree T(n, edge, 0);` で初期化
- 頂点列 `vector<int> vs` に対して `int r = T.query(vs);`
で補助的な木の根が返る．`vector<int> T.G[v]`
にその補助的な木に含まれる頂点の子が格納されている．
*/
struct AuxiliaryTree
{
  int n, dum;
  vi L, R, last, par; // L, R: eular tour 上で頂点 v が登場する最初/最後の位置
  vvi edge, G;
  LCA lca;
  AuxiliaryTree(int n, vvi edge, int root)
      : n(n), edge(edge), G(n), lca(n, edge, root), L(n, 0), R(n, 0), last(n, -1), par(n, -1)
  {
    dum = 0;
    dfs(0, -1);
  };

  void dfs(int v, int p)
  {
    par[v] = p;
    L[v] = dum;
    dum++;
    for (auto u : edge[v])
      if (u != p)
        dfs(u, v);
    R[v] = dum;
    dum++;
  }

  int query(vi vs)
  {
    assert(vs.size() != 0);
    sort(vs.begin(), vs.end(), [&](int u, int v)
         { return L[u] < L[v]; }); // pre-order で sort
    int sz = vs.size();
    rep(i, sz - 1) vs.push_back(lca.lca(vs[i], vs[i + 1]));
    sort(vs.begin(), vs.end(), [&](int u, int v)
         { return L[u] < L[v]; }); // pre-order で sort
    vi stc;
    int prv = -1;
    for (auto v : vs)
    {
      if (prv == v)
        continue;
      prv = v;
      while (!stc.empty() && R[stc.back()] < L[v])
        stc.pop_back();
      if (!stc.empty())
        G[stc.back()].push_back(v);
      G[v].clear();
      stc.push_back(v);
    }
    return stc[0];
  }
};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(20);

  int n;
  cin >> n;
  vvi G(n);
  vvi E(n - 1);
  rep(v, n)
  {
    int c;
    cin >> c;
    rep(c)
    {
      int e;
      cin >> e;
      e--;
      E[e].push_back(v);
    }
  }
  rep(e, n - 1)
  {
    int u = E[e][0], v = E[e][1];
    G[u].push_back(v);
    G[v].push_back(u);
  }

  AuxiliaryTree AT(n, G, 0);
  vi par = AT.par;
  vector<pair<int, int>> deg;
  rep(i, n)
  {
    deg.push_back({G[i].size(), i});
  }
  sort(deg.rbegin(), deg.rend());

  rep(q, 1, n)
  {
    vi vs;
    for (auto [d, v] : deg)
    {
      if (d >= q)
        vs.push_back(v);
      else
        break;
    }
    if (vs.size() == 0)
    {
      cout << "0" << " \n"[q + 1 == n];
      continue;
    }
    int r = AT.query(vs);
    unordered_map<int, int> mp;
    int ans = 0;
    auto dfs = [&](auto dfs, int v) -> void
    {
      for (auto u : AT.G[v])
      {
        dfs(dfs, u);
      }
      int x = (int)G[v].size() - mp[v];
      if (x >= q)
      {
        ans++;
        if (v != 0 && x == q)
        {
          mp[par[v]]++;
        }
      }
    };

    dfs(dfs, r);
    cout << ans << " \n"[q + 1 == n];
  }
}
0