Submission #893536

#	Time	Username	Problem	Language	Result	Execution time	Memory
893536		vjudge1	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1422 ms	40888 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int N = 2e5 + 1;

const int inf = 1e15;

int n;

struct SegTree{
    int T[N * 4];
    SegTree(){
        for ( int i = 0; i < N * 4; i++ ){
            T[i] = -inf;
        }
    }
    void upd(int v, int l, int r, int pos, int vl, bool set){
        if ( l == r ){
            if ( set ){
                T[v] = vl;
            } else chmax(T[v], vl);
            return;
        }
        int md = (l + r) >> 1;
        if ( pos <= md ){
            upd(v * 2, l, md, pos, vl, set);
        } else{
            upd(v * 2 + 1, md + 1, r, pos, vl, set);
        }
        T[v] = max(T[v * 2], T[v * 2 + 1]);
    }
    void upd(int pos, int vl, bool set){
        upd(1, 0, n, pos, vl, set);
    }
    int get(int v, int l, int r, int tl, int tr){
        if ( l > tr or r < tl ){
            return -inf;
        }
        if ( tl <= l && tr >= r ){
            return T[v];
        }
        int md = (l + r) >> 1;
        return max(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
    }
    int get(int l, int r){
        return get(1, 0, n, l, r);
    }
} seg;

vector <int> G[N];

int us[N], sub[N];

void dfs(int u, int p){
    sub[u] = 1;
    for ( auto &v: G[u] ){
        if ( v != p && !us[v] ){
            dfs(v, u);
            sub[u] += sub[v];
        }
    }
}

int find(int u, int p, int des){
    for ( auto &v: G[u] ){
        if ( v != p && !us[v] ){
            if ( sub[v] >= des / 2 ){
                return find(v, u, des);
            }
        }
    }
    return u;
}

vector <vector<ar<int,2>>> t;

int sz;


int ans[N * 2];

void dfs2(int u, int p, int d){
    chmax(ans[min(sz, sub[u]) * 2], d + 1); // with root
    t.back().pb({sub[u], d});
    for ( auto &v: G[u] ){
        if ( v != p && !us[v] ){
            dfs2(v, u, d + 1);
        }
    }
}
void decompose(int rt){
    dfs(rt, -1);
    int u = find(rt, -1, sub[rt]);
    dfs(u, -1);
    us[u] = true;
    for ( auto &v: G[u] ){
        if ( us[v] ) continue;
        sz = sub[u] - sub[v];
        t.pb({});
        dfs2(v, u, 1);
    }
//    if ( u == 6 ){
//        for ( auto &x: t ){
//            for ( auto &[s, d]: x ){
//                cout << "{" << s << ", " << d << "}, ";
//            } cout << ln;
//        } cout << ln;
//    }
    { // prefix
        for ( auto &x: t ){
            for ( auto &[s, d]: x ){
                chmax(ans[s * 2], seg.get(s, n) + d + 1);
            }
            for ( auto &[s, d]: x ){
                seg.upd(s, d, false);
            }
        }
        for ( auto &x: t ){
            for ( auto &[s, d]: x ){
                seg.upd(s, -inf, true);
            }
        }
    } // suffix
    {
        reverse(all(t));
        for ( auto &x: t ){
            for ( auto &[s, d]: x ){
                chmax(ans[s * 2], seg.get(s, n) + d + 1);
            }
            for ( auto &[s, d]: x ){
                seg.upd(s, d, false);
            }
        }
        for ( auto &x: t ){
            for ( auto &[s, d]: x ){
                seg.upd(s, -inf, true);
            }
        }
    } t.clear();
//    cout << "Root : " << u << ln;
//    for ( int i = 1; i <= n; i++ ){
//        cout << ans[i] << ' ';
//        ans[i] = 0;
//    } cout << ln;
    for ( auto &v: G[u] ){
        if ( !us[v] ){
            decompose(v);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1 - indexed
    cin >> n;
    for ( int i = 1; i < n; i++ ){
        int u, v; cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    decompose(1);
    for ( int i = n - (n & 1); i > 0; i -= 2 ){
        chmax(ans[i], ans[i + 2]);
    }
    for ( int i = 1; i <= n; i++ ){
        cout << (i & 1 ? 1LL : max(ans[i], 1LL)) << ln;
    }

    cout << '\n';
}

/*
7
1 7
3 2
2 6
5 6
6 4
4 7
*/

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