제출 #961041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961041		bebra	Cat Exercise (JOI23_ho_t4)	C++17	31 / 100	1551 ms	2496 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;




const int MAX_N = 6000 + 5;
const int MAX_K = 13;
vector<int> g[MAX_N];
bool used[MAX_N];

int tin[MAX_N];
int tout[MAX_N];
int timer = 0;

int binup[MAX_K][MAX_N];
int max_vertex[MAX_K][MAX_N];

int depth[MAX_N];

void dfs(int v) {
    tin[v] = timer++;
    for (auto u : g[v]) {
        g[u].erase(find(g[u].begin(), g[u].end(), v));

        binup[0][u] = v;
        max_vertex[0][v] = v;
        depth[u] = depth[v] + 1;
        dfs(u);
    }
    tout[v] = timer++;
}

bool is_parent(int p, int v) {
    return (tin[p] <= tin[v] && tout[v] <= tout[p]);
}

int lca(int u, int v) {
    if (is_parent(u, v)) return u;
    if (is_parent(v, u)) return v;

    for (int k = MAX_K - 1; k >= 0; --k) {
        if (!is_parent(binup[k][v], u)) {
            v = binup[k][v];
        }
    }
    return binup[0][v];
}

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

int max_v(int u, int v) {
    if (is_parent(u, v)) {
        v = binup[0][v];
        int w = depth[v] - depth[u];
        int res = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w & (1 << k)) {
                res = max(res, max_vertex[k][v]);
                v = binup[k][v];
            }
        }
        return res;
    } else if (is_parent(v, u)) {
        u = binup[0][u];
        int w = depth[u] - depth[v];
        int res = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w & (1 << k)) {
                res = max(res, max_vertex[k][u]);
                u = binup[k][u];
            }
        }
        return res;
    } else {
        v = binup[0][v];
        u = binup[0][u];

        int c = lca(u, v);
        int w1 = depth[u] - depth[c];
        int res1 = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w1 & (1 << k)) {
                res1 = max(res1, max_vertex[k][u]);
                u = binup[k][u];
            }
        }
        int w2 = depth[v] - depth[c];
        int res2 = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w2 & (1 << k)) {
                res2 = max(res2, max_vertex[k][v]);
                v = binup[k][v];
            }
        }
        return max(c, max(res1, res2));
    }
}

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

    int n;
    cin >> n;
    vector<int> p(n);
    for (auto& x : p) {
        cin >> x;
        --x;
    }

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;

        u = p[u];
        v = p[v];

        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(0);

    for (int k = 1; k < MAX_K; ++k) {
        for (int v = 0; v < n; ++v) {
            binup[k][v] = binup[k - 1][binup[k - 1][v]];
            max_vertex[k][v] = max(max_vertex[k - 1][v], max_vertex[k - 1][binup[k - 1][v]]);
        }
    }

    vector<int64_t> dp(n, -1e9);
    dp.back() = 0;
    int64_t res = 0;
    for (int v = n - 2; v >= 0; --v) {
        for (int u = v + 1; u < n; ++u) {
            // dbg(u);
            // dbg(v);
            // dbg(max_v(u, v));
            if (max_v(u, v) < min(u, v)) {
                dp[v] = max(dp[v], dp[u] + dist(u, v));
            }
        }
        res = max(res, dp[v]);
        // cerr << endl;
        // dbg(v);
        // dbg(dp[v]);
        // cerr << endl;
    }

    // dbg(max_v(2, 0));

    cout << res << '\n';
    
    return 0;
}


/*
16
16 8 7 9 1 5 3 13 11 15 12 10 2 4 14 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

22

*/

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26