Submission #1293192

#TimeUsernameProblemLanguageResultExecution timeMemory
1293192IcelastMeetings 2 (JOI21_meetings2)C++20
20 / 100
394 ms327680 KiB
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n+1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<vector<int>> d(n+1, vector<int>(n+1, 0));
    vector<vector<int>> sub(n+1, vector<int>(n+1, 0));
    for(int i = 1; i <= n; i++){
        auto dfs = [&](auto dfs, int u, int p) -> void{
            sub[i][u] = 1;
            for(int v : adj[u]){
                if(v == p) continue;
                d[i][v] = d[i][u] + 1;
                dfs(dfs, v, u);
                sub[i][u] += sub[i][v];
            }
        };
        dfs(dfs, i, 0);
    }
    vector<int> c(n+1, 1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j) continue;
            ll mn = min(sub[i][j], sub[j][i]);
            mn*=2;
            c[mn] = max(c[mn], d[i][j]+1);
        }
    }
    vector<int> ans(n+1);
    int mx = 0;
    for(int i = n; i >= 1; i--){
        if(i&1){
            ans[i] = 1;
            continue;
        }
        mx = max(mx, c[i]);
        ans[i] = mx;
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...