제출 #1271144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271144		chikien2009	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	328 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a, b;
int sz[200000], d[200000], res[200001];
vector<int> g[200000], v[200000];
pair<int, int> temp;

inline void DFS(int node, int par)
{
    sz[node] = 1;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS(i, node);
            sz[node] += sz[i];
        }
    }
}

inline int FindCenter(int node, int par)
{
    for (auto &i : g[node])
    {
        if (i != par && sz[i] * 2 > n)
        {
            return FindCenter(i, node);
        }
    }
    return node;
}

inline void DFS1(int node, int par, int depth)
{
    sz[node] = 1;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS1(i, node, depth + 1);
            sz[node] += sz[i];
        }
    }
    d[sz[node]] = max(d[sz[node]], depth);
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    DFS(0, 0);
    a = FindCenter(0, 0);
    fill_n(sz, n, 0);
    for (auto &i : g[a])
    {
        DFS1(i, a, 1);
        for (int j = sz[i] - 1; j >= 0; --j)
        {
            d[j] = max(d[j], d[j + 1]);
        }
        for (int j = 1; j <= sz[i]; ++j)
        {
            v[j].push_back(d[j]);
        }
        fill_n(d, sz[i], 0);
    }
    for (int i = 1; i * 2 <= n; ++i)
    {
        while (v[i].size() < 2)
        {
            v[i].push_back(0);
        }
        sort(v[i].begin(), v[i].end(), greater<int>());
        res[2 * i] = v[i][0] + v[i][1];
    }
    for (int i = 1; i <= n; ++i)
    {
        cout << res[i] + 1 << "\n";
    }
    return 0;
}

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