Submission #1028349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028349		underwaterkillerwhale	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	5212 KiB

meetings2

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const ll INF = 1e12;
const int BASE = 1337;

int n;
vector<int> ke[N];

namespace sub5 {
    int m;

    int nChild[N], par[N], high[N];
    int a[N];

    void pdfs (int u, int p) {
        nChild[u] = 1;
        par[u] = p;
        high[u] = high[p] + 1;
        iter (&v, ke[u]) {
            if (v != p) {
                pdfs (v, u);
                nChild[u] += nChild[v];
            }
        }
    }

    pair<int,int> FindDia () {
        int pt1, pt2, pt, Diameter = 0;
        function<void(int, int, int)> dfs  = [&] (int u, int p, int Dist) {
            if (Dist >= Diameter) {
                pt = u;
                Diameter = Dist;
            }
            iter (&v, ke[u]) if (v != p) {
                dfs (v, u, Dist + 1);
            }
        };
        dfs(1, 0, 0);
        pt1 = pt;
        dfs(pt1, 0, 0);
        pt2 = pt;
        return mp(pt1, pt2);
    }

    void solution() {
        int dia1, dia2;
        tie (dia1, dia2) = FindDia();
        pdfs (dia1, 0);
        int prv = -1;
        while (par[dia1] != dia2) {
            int delta = nChild[dia2];
            if (prv != -1)
                delta -= nChild[prv];
            a[++m] = delta;
            prv = dia2;
            dia2 = par[dia2];
        }
        int L = 1, R = m, pre = 1, suf = 1;
        rep (k, 1, n) {
            if (k & 1) cout << 1 <<"\n";
            else {
                while (L < R && pre < k / 2) {
                    pre += a[++L];
                }
                while (R > L && suf < k / 2) {
                    suf += a[--R];
                }
//                assert(pre >= k/2 && suf >= k/2);
                if (pre < k / 2 || suf < k / 2) cout << 1 <<"\n";
                else cout << R - L + 1 <<"\n";
            }
        }


    }
}

void solution () {
    cin >> n;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
//    pdfs(1, 0);
//    if (n <= 4000)
        sub5 :: solution();
//    rep (i, 1, n) {
//        if (i & 1) cout << 1 <<"\n";
//        else {
//            cout << Diameter <<"\n";
//            Diameter -= 2;
//        }
//    }

}
#define file(name) freopen(name".inp", "r", stdin); \
//freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
5 10
798981764 -961045489
-762214604 -6816243
549909709 362471127
504233152 -881315415
503023672 -79630788
*/

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