제출 #804137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804137		vjudge1	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	4 ms	7380 KiB

meetings2

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e5 + 10;
const int INF = 1e9;
vector<int> g[N];

int n;
int sz[N];
int anc[N][20];
int tin[N], tout[N], T, depth[N];
void precalc(int s, int p) {
    sz[s] = 1;
    anc[s][0] = p;
    tin[s] = T++;
    for(int i = 1; i < 20; i++) 
        anc[s][i] = anc[anc[s][i - 1]][i - 1];
    for(int to : g[s]) {
        if(to == p) continue;
        depth[to] = depth[s] + 1;
        precalc(to, s);
        sz[s] += sz[to];
    }
    tout[s] = T++;
}
bool up(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
    if(up(u, v)) return u;
    if(up(v, u)) return v;
    for(int i = 19; i >= 0; i--) {
        if(!up(anc[u][i], v)) u = anc[u][i];
    }
    return anc[u][0];
}
int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int find_centroid(int s, int p) {
    for(int to : g[s]) {
        if(to == p) continue;
        if(sz[to] * 2 > n) return find_centroid(to, s);
    }
    return s;
}
int curK = 0, res = 0;
int f[N];
void dfs(int s, int p) {
    f[s] = -INF;
    if(sz[s] >= curK) f[s] = 0;
    int mx0 = -INF, mx1 = -INF;

    for(int to : g[s]) {
        if(to == p) continue;
        dfs(to, s);
        if(f[to] > mx0) mx1 = mx0, mx0 = f[to];
        else if(f[to] > mx1) mx1 = f[to];
        f[s] = max(f[s], f[to] + 1);
    }
    res = max(res, mx0 + mx1 + 2);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    precalc(1, 1);
    int root = find_centroid(1, 1);
    precalc(root, root);
    for(int k = 1; k <= n; k++) {
        if(k % 2 == 1) {
            cout << 1 << '\n';
            continue;
        }
        res = 1; curK = k / 2;
        dfs(root, root);
        cout << res+1 << '\n';
    }
}

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