CF379F New Year Tree

SunnyYuan的博客 / 2024-08-09 / 原文

题意

给定图：

每次在叶子结点加入两个点，并实时输出树的直径长度。

思路

每次增加两个点，直径至多变化一个点，长度最多加 1，所以对加入的点处理 lca，并且更新长度和点即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int fa[30][N], dep[N];

void process(int u) {
    for (int i = 1; i < 30; i++) {
        fa[i][u] = fa[i - 1][fa[i - 1][u]];
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);

    for (int j = 29; j >= 0; j--) {
        if (dep[fa[j][u]] >= dep[v]) u = fa[j][u];
    }
    if (u == v) return u;

    for (int j = 29; j >= 0; j--) {
        if (fa[j][u] != fa[j][v]) {
            u = fa[j][u];
            v = fa[j][v];
        }
    }
    return fa[0][u];
}

int dis(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    fa[0][2] = fa[0][3] = fa[0][4] = 1;
    dep[2] = dep[3] = dep[4] = 1;
    int a1 = 2, a2 = 3, res = 2, ver = 5;

    for (int opt = 1; opt <= q; opt++) {
        int x;
        cin >> x;
        fa[0][ver] = fa[0][ver + 1] = x;
        dep[ver] = dep[ver + 1] = dep[x] + 1;
        process(ver);
        process(ver + 1);
        int len1 = dis(a1, ver);
        int len2 = dis(a2, ver);
        int len3 = dis(a1, ver + 1);
        int len4 = dis(a2, ver + 1);
        if (len1 > res) {
            res = len1;
            a2 = ver;
        }
        else if (len2 > res) {
            res = len2;
            a1 = ver;
        }
        else if (len3 > res) {
            res = len3;
            a2 = ver + 1;
        }
        else if (len4 > res) {
            res = len4;
            a1 = ver + 1;
        }
        cout << res << '\n';
        ver += 2;
    }
    return 0;
}