TIOJ 2219：長頸鹿園

TIOJ 2219：長頸鹿園

題目大意：給你 $n$ 個點，在第 $i$ 天第 $i$ 個點會被加入樹中，輸出 $n$ 個數字代表在第 $i$ 天的樹直徑數量。

解法：這邊有官解。然後這邊有一個用重心剖分的方法，就是如果加入這點直徑會變長，那答案就是以這點為端點的直徑數量，否則就是原本的答案加上以這點為端點的直徑數量。

我的作法是先記錄好每個點在重心樹上的深度、在深度 $i$ 時對應到的重心、與重心的距離和屬於重心的哪一個子樹。然後在加入點時，紀錄每個重心距離最遠、次遠的點的距離和數量，與每一個在深度 $i$ 時的子樹的最遠節點與數量。每次就從深度 $1$ 一直更新到自己為重心，然後細節蠻繁瑣的，$\text{debug}$ 很久。最終複雜度為一開始建立重心樹的 $O(n\times log(n))$ 加上加了 $n$ 個點，每個點更新 $log(n)$ 層，每層 $O(1)$，也是 $O(n\times log(n))$，最終複雜度 $O(n\times log(n))$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for (int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;
const int H = __lg (SIZE) + 2;

int n;
vector<int> adj[SIZE];

int siz, cent;
int cd[SIZE];
int w[SIZE];
int c[SIZE][H + 1], dep[SIZE][H + 1], gfa[SIZE][H + 1];

void fw (int pos, int fa) {
    siz++;
    for (int np : adj[pos]) {
        if (np == fa || cd[np]) continue;
        fw (np, pos);
    }
}

void fc (int pos, int fa) {
    w[pos] = 1;
    int mx = 0;
    for (int np : adj[pos]) {
        if (np == fa || cd[np]) continue;
        fc (np, pos);
        w[pos] += w[np];
        mx = max (mx, w[np]);
    }
    mx = max (mx, siz - w[pos]);
    if (mx <= siz / 2) cent = pos;
}

void dfs (int pos, int fa, int g, int d) {
    c[pos][cd[cent]] = cent;
    dep[pos][cd[cent]] = d;
    gfa[pos][cd[cent]] = g;
    for (int np : adj[pos]) {
        if (np == fa || cd[np]) continue;
        dfs (np, pos, g, d + 1);
    }
}

void divide (int pos, int d) {
    siz = 0, fw (pos, pos);
    fc (pos, pos);
    cd[cent] = d;
    c[cent][d] = gfa[cent][d] = cent;
    for (int np : adj[cent]) {
        if (cd[np]) continue;
        dfs (np, np, np, 1);
    }
    for (int np : adj[cent]) {
        if (cd[np]) continue;
        divide (np, d + 1);
    }
}

int len;
ll ans = 1;
pair<pair<int, int>, pair<int, int>> pmx[SIZE];
pair<int, int> dmx[SIZE][H + 1];

pair<int, int> update (int pos) {
    int mx = 0, cnt = 0;
    FOR (i, 1, cd[pos]) {
        cent = c[pos][i];
        int d = dep[pos][i], g = gfa[pos][i], tmp = 0, tcnt = 0;
        auto &[p1, p2] = pmx[cent];
        auto &[m1, c1] = p1;
        auto &[m2, c2] = p2;
        auto &[dm, dc] = dmx[g][i];
        if (d == dm) {
            dc++;
            if (dm == m1) c1++;
            else if (dm == m2) c2++;
        } else if (d > dm) {
            if (dm == m1) c1 -= dc;
            else if (dm == m2) c2 -= dc;
            dm = d, dc = 1;
            if (dm == m1) c1++;
            else if (dm == m2) c2++;
        }
        if (dm > m1) {
            if (c1) m2 = m1, c2 = c1;
            m1 = dm, c1 = dc;
        } else if (m1 > dm && dm > m2) {
            m2 = dm, c2 = dc;
        }
        if (d == dm) {
            if (dm == m1) {
                if (c1 > dc) tmp = m1 + m1, tcnt = c1 - dc;
                else if (c2) tmp = m1 + m2, tcnt = c2;
            } else if (dm == m2) {
                tmp = m1 + m2, tcnt = c1;
            }
        }
        if (tmp > mx) mx = tmp, cnt = tcnt;
        else if (tmp == mx) cnt += tcnt;
    }
    return {mx, cnt};
}

void solve() {
    cin >> n;
    FOR (i, 2, n) {
        int fa;
        cin >> fa;
        adj[fa].pb (i);
        adj[i].pb (fa);
    }
    divide (1, 1);
    FOR (i, 1, n) {
        auto [mx, num] = update (i);
        if (mx == len) ans += num;
        else if (mx > len) ans = num, len = mx;
        cout << ans << '\n';
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！