結果
| 問題 | No.3405 Engineering University of Tree |
| コンテスト | |
| ユーザー |
 apricity
|
| 提出日時 | 2025-12-13 02:43:24 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 16,920 bytes |
| 記録 | |
| コンパイル時間 | 3,624 ms |
| コンパイル使用メモリ | 241,892 KB |
| 実行使用メモリ | 77,824 KB |
| 最終ジャッジ日時 | 2025-12-13 02:43:37 |
| 合計ジャッジ時間 | 11,504 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 14 WA * 1 TLE * 1 -- * 5 |
ソースコード
#ifdef LOCAL
#include "template.hpp"
#else
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<utility>
#include<tuple>
#include<array>
#include<cstdint>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<cctype>
#include<chrono>
#include<random>
#include<cassert>
#include<cstddef>
#include<iterator>
#include<string_view>
#include<type_traits>
#include<functional>
using namespace std;
namespace io {
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (auto &x : v) is >> x;
return is;
}
template <typename T, size_t N = 0>
istream &operator>>(istream &is, array<T, N> &v) {
for (auto &x : v) is >> x;
return is;
}
template <size_t N = 0, typename T>
istream& cin_tuple_impl(istream &is, T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
is >> x;
cin_tuple_impl<N + 1>(is, t);
}
return is;
}
template <class... T>
istream &operator>>(istream &is, tuple<T...> &t) {
return cin_tuple_impl(is, t);
}
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << p.first << " " << p.second;
return os;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &v) {
size_t n = v.size();
for (size_t i = 0; i < n; i++) {
if (i) os << " ";
os << v[i];
}
return os;
}
template <size_t N = 0, typename T>
ostream& cout_tuple_impl(ostream &os, const T &t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) os << " ";
const auto &x = std::get<N>(t);
os << x;
cout_tuple_impl<N + 1>(os, t);
}
return os;
}
template <class... T>
ostream &operator<<(ostream &os, const tuple<T...> &t) {
return cout_tuple_impl(os, t);
}
void in() {}
template<typename T, class... U>
void in(T &t, U &...u) {
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template<typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u) {
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
void outr() {}
template<typename T, class... U, char sep = ' '>
void outr(const T &t, const U &...u) {
cout << t;
outr(u...);
}
void __attribute__((constructor)) _c() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} // namespace io
using io::in;
using io::out;
using io::outr;
#define SHOW(x) static_cast<void>(0)
using ll = long long;
using D = double;
using LD = long double;
using P = pair<ll, ll>;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using vi = vector<ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T> using vvvc = vector<vvc<T>>;
template <class T> using vvvvc = vector<vvvc<T>>;
template <class T> using vvvvvc = vector<vvvvc<T>>;
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
template<typename T> using PQ = priority_queue<T,vector<T>>;
template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;
#define rep1(a) for(ll i = 0; i < a; i++)
#define rep2(i, a) for(ll i = 0; i < a; i++)
#define rep3(i, a, b) for(ll i = a; i < b; i++)
#define rep4(i, a, b, c) for(ll i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(a) for(ll i = (a)-1; i >= 0; i--)
#define rrep2(i, a) for(ll i = (a)-1; i >= 0; i--)
#define rrep3(i, a, b) for(ll i = (b)-1; i >= a; i--)
#define rrep4(i, a, b, c) for(ll i = (b)-1; i >= a; i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define for_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define SZ(v) ll(v.size())
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(c, x) distance((c).begin(), lower_bound(ALL(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(ALL(c), (x)))
template <typename T, typename U>
T SUM(const vector<U> &v) {
T res = 0;
for(auto &&a : v) res += a;
return res;
}
template <typename T>
vector<pair<T,int>> RLE(const vector<T> &v) {
if (v.empty()) return {};
T cur = v.front();
int cnt = 1;
vector<pair<T,int>> res;
for (int i = 1; i < (int)v.size(); i++) {
if (cur == v[i]) cnt++;
else {
res.emplace_back(cur, cnt);
cnt = 1; cur = v[i];
}
}
res.emplace_back(cur, cnt);
return res;
}
template<class T, class S>
inline bool chmax(T &a, const S &b) { return (a < b ? a = b, true : false); }
template<class T, class S>
inline bool chmin(T &a, const S &b) { return (a > b ? a = b, true : false); }
void YESNO(bool flag) { out(flag ? "YES" : "NO"); }
void yesno(bool flag) { out(flag ? "Yes" : "No"); }
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityl(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityl(x) & 1 ? -1 : 1); }
int highbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int highbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int highbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int highbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T get_bit(T x, int k) { return x >> k & 1; }
template <typename T>
T set_bit(T x, int k) { return x | T(1) << k; }
template <typename T>
T reset_bit(T x, int k) { return x & ~(T(1) << k); }
template <typename T>
T flip_bit(T x, int k) { return x ^ T(1) << k; }
template <typename T>
T popf(deque<T> &que) { T a = que.front(); que.pop_front(); return a; }
template <typename T>
T popb(deque<T> &que) { T a = que.back(); que.pop_back(); return a; }
template <typename T>
T pop(queue<T> &que) { T a = que.front(); que.pop(); return a; }
template <typename T>
T pop(stack<T> &que) { T a = que.top(); que.pop(); return a; }
template <typename T>
T pop(PQ<T> &que) { T a = que.top(); que.pop(); return a; }
template <typename T>
T pop(minPQ<T> &que) { T a = que.top(); que.pop(); return a; }
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
ll mid = (ok + ng) / 2;
(check(mid) ? ok : ng) = mid;
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 60) {
for (int _ = 0; _ < iter; _++) {
double mid = (ok + ng) / 2;
(check(mid) ? ok : ng) = mid;
}
return (ok + ng) / 2;
}
// max x s.t. b*x <= a
ll div_floor(ll a, ll b) {
assert(b != 0);
if (b < 0) a = -a, b = -b;
return a / b - (a % b < 0);
}
// max x s.t. b*x < a
ll div_under(ll a, ll b) {
assert(b != 0);
if (b < 0) a = -a, b = -b;
return a / b - (a % b <= 0);
}
// min x s.t. b*x >= a
ll div_ceil(ll a, ll b) {
assert(b != 0);
if (b < 0) a = -a, b = -b;
return a / b + (a % b > 0);
}
// min x s.t. b*x > a
ll div_over(ll a, ll b) {
assert(b != 0);
if (b < 0) a = -a, b = -b;
return a / b + (a % b >= 0);
}
// x = a mod b (b > 0), 0 <= x < b
ll modulo(ll a, ll b) {
assert(b > 0);
ll c = a % b;
return c < 0 ? c + b : c;
}
// (q,r) s.t. a = b*q + r, 0 <= r < b (b > 0)
// div_floor(a,b), modulo(a,b)
pair<ll,ll> divmod(ll a, ll b) {
ll q = div_floor(a,b);
return {q, a - b*q};
}
#endif
template<typename T, typename F>
struct SparseTable {
F f;
vector<vector<T>> v;
vector<int> lookup;
explicit SparseTable() = default;
explicit SparseTable (const vector<T> &a, const F &f) : f(f){
const int n = (int)a.size();
const int lg = 32-__builtin_clz(n);
v.assign(lg, vector<T>(n));
for(int i = 0; i < n; i++) v[0][i] = a[i];
for(int i = 1; i < lg; i++){
for(int j = 0; j+(1<<i) <= n; j++){
v[i][j] = f(v[i-1][j], v[i-1][j+(1<<(i-1))]);
}
}
lookup.resize(n+1);
for (int i = 2; i < (int)lookup.size(); i++) {
lookup[i] = lookup[i >> 1] + 1;
}
}
inline T fold(int l, int r) const {
int b = lookup[r-l];
return f(v[b][l], v[b][r-(1<<b)]);
}
};
struct PlusMinusOneRMQ {
int s;
vector<int> v;
vector<int> block_min_index, block_pm_bit, lg_table;
vector<vector<int>> spt;
vector<vector<vector<int>>> lookup;
explicit PlusMinusOneRMQ() = default;
explicit PlusMinusOneRMQ(const vector<int> &v): v(v) {
int n = v.size();
s = max(1, (31 - __builtin_clz(n)) / 2);
int b = (n + s - 1) / s;
int lg = 32 - __builtin_clz(b);
block_min_index.assign(b, -1);
block_pm_bit.assign(b, 0);
lg_table.assign(b + 1, 0);
spt.assign(lg, vector<int>(b));
lookup.assign(1 << (s - 1), vector<vector<int>> (s, vector<int> (s + 1)));
for (int i = 2; i <= b; i++) lg_table[i] = lg_table[i >> 1] + 1;
for (int i = 0, l = 0; i < b; i++, l += s) {
int r = min(n, l + s);
block_min_index[i] = l;
for (int j = l + 1; j < r; j++) {
if (v[j] < v[block_min_index[i]]) block_min_index[i] = j;
if (v[j - 1] < v[j]) block_pm_bit[i] |= 1 << (j - l - 1);
}
}
for (int i = 0; i < b; i++) spt[0][i] = block_min_index[i];
for (int i = 1; i < lg; i++) {
for (int j = 0; j + (1 << i) <= b; j++) {
spt[i][j] = (v[spt[i - 1][j]] < v[spt[i - 1][j + (1 << (i - 1))]] ?
spt[i - 1][j] : spt[i - 1][j + (1 << (i - 1))]);
}
}
for (int bit = 0; bit < (1 << (s - 1)); bit++) {
for (int l = 0; l < s; l++) {
int cur = 0, min_val = 0, min_pos = l;
for (int r = l + 1; r <= s; r++) {
lookup[bit][l][r] = min_pos;
if (bit >> (r - 1) & 1) cur++;
else cur--;
if (cur < min_val) {
min_val = cur;
min_pos = r;
}
}
}
}
};
inline int fold(int l, int r) const {
assert(l < r);
int li = l / s;
int ri = r / s;
if (li == ri) return lookup[block_pm_bit[li]][l % s][r % s] + li * s;
int ret = lookup[block_pm_bit[li]][l % s][s] + li * s;
if (r % s > 0) {
int right = lookup[block_pm_bit[ri]][0][r % s] + ri * s;
if (v[right] < v[ret]) ret = right;
}
if (li + 1 != ri) {
int layer = lg_table[ri - li - 1];
int mid = v[spt[layer][li + 1]] < v[spt[layer][ri - (1 << layer)]] ?
spt[layer][li + 1] : spt[layer][ri - (1 << layer)];
if (v[mid] < v[ret]) ret = mid;
}
return ret;
}
};
struct RMQLowestCommonAncestor {
vector<int> et,dep,tin;
// using F = function<int(int,int)>;
// SparseTable<int,F> st;
PlusMinusOneRMQ st;
const vector<vector<int>> &g;
RMQLowestCommonAncestor (const vector<vector<int>> &g): g(g){}
void init (int root = 0) {
const int n = g.size();
et.reserve(n*2-1);
dep.reserve(n*2-1);
tin.resize(n);
dfs(root, -1, 0);
// vector<int> vs(n*2-1);
// iota(ALL(vs),0);
// F f = [&](int a, int b) {return dep[a] < dep[b] ? a:b;};
// st = SparseTable<int, F> (vs, f);
st = PlusMinusOneRMQ(dep);
}
void dfs(int u, int p, int d){
tin[u] = (int)et.size();
et.emplace_back(u);
dep.emplace_back(d);
for(int v : g[u]) if(v != p){
dfs(v, u, d+1);
et.emplace_back(u);
dep.emplace_back(d);
}
}
int lca(int x, int y) const{
if(tin[x] > tin[y]) swap(x,y);
return x == y ? x : et[st.fold(tin[x],tin[y])];
}
int dist (int u, int v) const{
int w = lca(u,v);
return dep[tin[u]]+dep[tin[v]]-dep[tin[w]]*2;
}
};
struct AuxiliaryTree : RMQLowestCommonAncestor{
vector<vector<int>> ret;
AuxiliaryTree(const vector<vector<int>> &g) : RMQLowestCommonAncestor(g), ret(g.size()) {
RMQLowestCommonAncestor::init();
}
int build(vector<int> &vs) {
const int k = vs.size();
if (k == 0) return -1;
// sort(ALL(vs), [&](int i, int j){
// return tin[i] < tin[j];
// });
stack<int> stk;
stk.emplace(vs[0]);
for(int i = 0; i < k-1; i++){
int w = lca(vs[i], vs[i+1]);
if (w != vs[i]){
int last = stk.top(); stk.pop();
while (!stk.empty() and dep[tin[w]] < dep[tin[stk.top()]]){
ret[stk.top()].emplace_back(last);
last = stk.top();
stk.pop();
}
if (stk.empty() or stk.top() != w){
stk.emplace(w);
vs.emplace_back(w);
}
ret[w].emplace_back(last);
}
stk.emplace(vs[i+1]);
}
while(stk.size()>1){
int l = stk.top(); stk.pop();
ret[stk.top()].emplace_back(l);
}
return stk.top();
}
void clear(const vector<int> &vs){
for(int v : vs) ret[v].clear();
}
};
void solve() {
int n; in(n);
vc<P> e(n-1, {-1,-1});
vc<int> d(n);
vv(int,g,n);
rep(i,n){
in(d[i]);
rep(j,d[i]){
int ej; in(ej); ej--;
if(e[ej].first == -1) e[ej].first = i;
else e[ej].second = i;
}
}
for(auto [x,y] : e){
assert(x != -1);
assert(y != -1);
g[x].emplace_back(y);
g[y].emplace_back(x);
}
vc<int> ans(n-1);
AuxiliaryTree at(g);
vv(int, vd, n);
rep(i,n*2-1) {
int v = at.et[i];
if(at.tin[v] == i) vd[d[v]].emplace_back(v);
}
vc<int> vs1;
rrep(k,1,n){
vc<int> vs2;
merge(ALL(vs1), ALL(vd[k]), back_inserter(vs2), [&](int u, int v){return at.tin[u] < at.tin[v];});
if(vs2.empty()) continue;
int r = at.build(vs2);
auto rec = [&] (auto rec, int u) -> pair<int,bool> {
int ss = 0;
int available = 0;
int all = 0;
for(int v : at.ret[u]) {
all++;
auto [x,y] = rec(rec, v);
ss += x;
if(d[v] < k or !y or at.dist(u,v) > 1) available++;
}
if(u != r){
available += (d[u] - 1 - all);
if(available >= k) return {ss+1, false};
else if(available == k-1) return {ss+1, true};
else return {ss, false};
}
else{
available += (d[u] - all);
if(available >= k) return {ss+1, false};
else return {ss, false};
}
};
ans[k-1] = rec(rec, r).first;
at.clear(vs2);
vs1.swap(vs2);
}
out(ans);
}
int main() {
int tc = 1;
// in(tc);
while(tc--){
solve();
}
}