結果

問題 No.3405 Engineering University of Tree
コンテスト
ユーザー umimel
提出日時 2025-12-12 09:36:57
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 8,526 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,856 ms
コンパイル使用メモリ 208,068 KB
実行使用メモリ 114,228 KB
最終ジャッジ日時 2025-12-12 09:37:13
合計ジャッジ時間 15,983 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 WA * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:264:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  264 |         for(auto [d, v] : sdeg){
      |                  ^

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;


template<typename T> 
struct edge{
    int from;
    int to;
    T cost;
    int id;

    edge(){}
    edge(int to, T cost=1) : from(-1), to(to), cost(cost){}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
    edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}

    void reverse(){swap(from, to);}
};

template<typename T>
struct edges : std::vector<edge<T>>{
    void sort(){
        std::sort(
            (*this).begin(),
            (*this).end(), 
            [](const edge<T>& a, const edge<T>& b){
                return a.cost < b.cost;
            }
        );
    }
};

template<typename T = bool>
struct graph : std::vector<edges<T>>{
private:
    int n = 0;
    int m = 0;
    edges<T> es;
    bool dir;

public:
    graph(int n, bool dir) : n(n), dir(dir){
        (*this).resize(n);
    }

    void add_edge(int from, int to, T cost=1){
        if(dir){
            es.push_back(edge<T>(from, to, cost, m));
            (*this)[from].push_back(edge<T>(from, to, cost, m++));
        }else{
            if(from > to) swap(from, to);
            es.push_back(edge<T>(from, to, cost, m));
            (*this)[from].push_back(edge<T>(from, to, cost, m));
            (*this)[to].push_back(edge<T>(to, from, cost, m++));
        }
    }

    int get_vnum(){
        return n;
    }

    int get_enum(){
        return m;
    }

    bool get_dir(){
        return dir;
    }

    edge<T> get_edge(int i){
        return es[i];
    }

    edges<T> get_edge_set(){
        return es;
    }
};

template<typename T>
struct redge{
    int from, to;
    T cap, cost;
    int rev;
    
    redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}
    redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}
};

template<typename T> using Edges = vector<edge<T>>;
template<typename T> using weighted_graph = vector<Edges<T>>;
template<typename T> using tree = vector<Edges<T>>;
using unweighted_graph = vector<vector<int>>;
template<typename T> using residual_graph = vector<vector<redge<T>>>;


template<typename W>
struct lowest_common_ancestor{
    int root = 0;
    int n;
    int log_n = 1;
    vector<vector<int>> par;
    vector<int> depth;

    lowest_common_ancestor(){}
    lowest_common_ancestor(tree<W> &T, int root=0) : root(root){
        n = (int)T.size();
        while((1 << log_n) < n) log_n++;
        par.resize(log_n, vector<int>(n, -1));
        depth.resize(n, 0);
        init(T);
    }

    void init(tree<W> &T){
        function<void(int, int)> dfs = [&](int v, int p){
            par[0][v] = p;
            for(edge<W> e : T[v]) if(e.to!=p){
                depth[e.to] = depth[v]+1;
                dfs(e.to, v);
            }
        };

        dfs(root, -1);
        for(int k=0; k+1<log_n; k++){
            for(int v=0; v<n; v++){
                if(par[k][v]<0) par[k+1][v] = -1;
                else par[k+1][v] = par[k][par[k][v]];
            }
        }
    }

    int query(int u, int v){
        if(depth[u] < depth[v]) swap(u, v);
        for(int k=0; k<log_n; k++) if((depth[u]-depth[v]) >> k & 1) u = par[k][u];

        if(u == v) return u;
        for(int k=log_n-1; k>=0; k--){
            if(par[k][u] != par[k][v]){
                u = par[k][u];
                v = par[k][v];
            }
        }

        return par[0][u];
    }
};


template<typename W>
struct auxiliary_tree{
    int n;
    vector<int> in;
    int root;
    lowest_common_ancestor<W> lca;

    auxiliary_tree(tree<W> &T, int root = 0) : root(root){
        n = (int)T.size();
        in.resize(n);
        euler_tour(T);
        lca = lowest_common_ancestor<W>(T, root);
    }

    void euler_tour(tree<W> &T){
        int now = 0;
        function<void(int, int)> dfs = [&](int v, int p){
            in[v] = now++;
            for(edge<W> e : T[v]) if(e.to != p) dfs(e.to, v);
        }; dfs(root, -1);
    }

    int build(int k, vector<int> &vs, tree<W> &AT){
        sort(vs.begin(), vs.end(), [&](int i, int j){return in[i] < in[j];});
        stack<int> stk;
        stk.push(vs[0]);
        AT[vs[0]] = {};

        for(int i=0; i<k-1; i++){
            int r = lca.query(vs[i], vs[i+1]);

            if(r != vs[i]){
                int last = stk.top();
                stk.pop();
                while(!stk.empty()&&lca.depth[r]<lca.depth[stk.top()]){
                    AT[stk.top()].push_back(edge<W>(last));
                    last = stk.top();
                    stk.pop();
                }

                if(stk.empty()||stk.top()!=r){
                    stk.push(r);
                    vs.push_back(r);
                    AT[r] = {edge<W>(last)};
                }else{
                    AT[r].push_back(edge<W>(last));
                }
            }

            stk.push(vs[i+1]);
            AT[vs[i+1]] = {};
        }

        int r = stk.top();
        while(!stk.empty()){
            stk.pop();
            if(!stk.empty()){
                AT[stk.top()].push_back(edge<W>(r));
                r = stk.top();
            }
        }

        function<void(int, int)> dfs = [&](int v, int p){
            for(edge<int> e : AT[v]) if(e.to != p){
                AT[e.to].push_back(edge<int>(v));
                dfs(e.to, v);
            }
        }; dfs(r, -1);

        return r;
    }
};


void solve(){
    int n; cin >> n;
    tree<int> T(n);
    vector<pair<int, int>> sdeg(n);
    vector<int> deg(n);
    vector<vector<int>> es(n-1);
    for(int v=0; v<n; v++){
        int c; cin >> c;
        sdeg[v] = {c, v};
        deg[v] = c;
        for(int i=0; i<c; i++){
            int id; cin >> id;
            id--;
            es[id].push_back(v);
        }
    }
    for(auto vec : es){
        T[vec[0]].pb(vec[1]);
        T[vec[1]].pb(vec[0]);
    }
    sort(all(sdeg), greater<pair<int, int>>());

    auxiliary_tree<int> auxiliary_tree(T, 0);
    tree<int> AT(n);
    // dp[v][0]:=頂点vで頂点vの親との辺を使わない
    // dp[v][1]:=頂点vで頂点vの親との辺を使う
    vector<vector<int>> dp(n, vector<int>(2, 0));
    for(int q=1; q<n; q++){
        vector<int> vs;
        for(auto [d, v] : sdeg){
            if(q <= d) vs.push_back(v);
            else break;
        }
        if(vs.empty()){
            cout << 0 << " ";
            continue;
        }
  
        auxiliary_tree.build(vs.size(), vs, AT);
        vector<int> vs2;
        for(int v : vs) for(auto e : AT[v]) vs2.push_back(e.to), vs2.push_back(v);
        vs = vs2;
        sort(all(vs));
        vs.erase(unique(all(vs)), vs.end());
        function<void(int, int)> dfs = [&](int v, int p){
            vector<int> diff;
            int sum = 0;
            for(auto e : AT[v]) if(e.to != p){
                dfs(e.to, v);
                diff.push_back(dp[e.to][0]-dp[e.to][1]);
                sum += dp[e.to][1];
            }
            sort(all(diff), greater<int>());

            if(v == vs[0]){
                // calc dp[0]
                if(q <= deg[v]){
                    dp[v][0] = 1 + sum;
                    for(int i=0; i<min(q, (int)diff.size()); i++) dp[v][0] += diff[i];
                }
                dp[v][0] = max(dp[v][0], sum);
            }else{
                // calc dp[0]
                if(q+1 <= deg[v]){
                    dp[v][0] = 1 + sum;
                    for(int i=0; i<min(q, (int)diff.size()); i++) dp[v][0] += diff[i];
                }else{
                    dp[v][0] = sum;
                }
                // calc dp[1]
                if(q <= deg[v]){
                    dp[v][1] = 1 + sum;
                    for(int i=0; i<min(q-1, (int)diff.size()); i++) dp[v][1] += diff[i];
                }
            }
        }; dfs(vs[0], -1);

        cout << dp[vs[0]][0] << " ";

        // erase
        for(int v : vs) AT[v].clear();
        for(int v : vs) dp[v][0] = dp[v][1] = 0;
    }
    cout << "\n";
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T=1;
    //cin >> T;
    while(T--) solve();
}
0