Submission #1042789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042789		SoulKnight	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	120 ms	70244 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'

const int N = 2e5 + 5;

const int LG = 20;
int n, glit = 1, root, p[N], mx[LG][N], up[LG][N], where[N], sz[N];
vector<int> adj[N];

int dfs(int u, int par){
    up[0][u] = par;
    mx[0][glit] = u;

    where[u] = glit;
    glit++;

    int tot = 1;
    for (auto v: adj[u]){
        if (v == par) continue;
        tot += dfs(v, u);
    }
    sz[where[u]] = tot;
    return tot;
}

int answer(int l, int r){
    if (l > r) return 0;
    int lg = log2(r-l+1);
    return p[mx[lg][l]] > p[mx[lg][r-(1<<lg)+1]]? mx[lg][l]: mx[lg][r-(1<<lg)+1];
}

bool is_ancestor(int u, int v){
    return where[u] <= where[v] && where[v] <= where[u] + sz[where[u]] - 1;
}

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

    for (int i = LG-1; i >= 0; i--){
        if (!is_ancestor(up[i][u], v)) u = up[i][u];
    }
    return up[0][u];
}

ll dist(int u, int v){
    int ances = lca(u, v);
    ll ans = 0;
    for (int i = LG-1; i >= 0; i--){
        if (!is_ancestor(up[i][u], ances)) {ans += (1 << i); u = up[i][u];}
        if (!is_ancestor(up[i][v], ances)) {ans += (1 << i); v = up[i][v];}
    }

    return ans + (u != ances) + (v != ances);
}




ll f(int l, int r, int u){
    // cout << l << ' ' << r << ' ' << u << ln;

    int nxt;
    ll ans = 0LL;

    // go to top
    nxt = answer(l, min(r, where[u]-1));
    if (nxt) ans = max(ans, dist(u, nxt) + f(l, min(r, where[u]-1), nxt));

    nxt = answer(max(l, where[u] + sz[where[u]]), r);
    if (nxt) ans = max(ans, dist(u, nxt) + f(max(l, where[u] + sz[where[u]]), r, nxt));


    // go to subtree
    for (auto v: adj[u]){
        if (v == up[0][u]) continue;
        nxt = answer(max(l, where[v]), min(r, where[v] + sz[where[v]] - 1));
        if (!nxt) continue;

        ans = max(ans, dist(u, nxt) + f(max(l, where[v]), min(r, where[v] + sz[where[v]] - 1), nxt));
    }

    return ans;
}



void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    root = -1;
    for (int i = 1; i <= n; i++) if (p[i] == n) root = i;
    dfs(root, root);


    for (int i = 1; i < LG; i++){
        for (int j = 1; j <= n; j++) up[i][j] = up[i-1][up[i-1][j]];
        for (int j = 1; j + (1 << (i-1)) <= n; j++){
            mx[i][j] = (p[mx[i-1][j]] > p[mx[i-1][j + (1 << (i-1))]])? mx[i-1][j]: mx[i-1][j + (1 << (i-1))];
        }
    }

    cout << f(1, n, root) << ln;

}

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

    // int TT; cin >> TT;
    // while (TT--) {solve();}

    solve();

}

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