제출 #1190972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190972		M_W_13	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	149 ms	41136 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
const int MAXN = 2e5 + 7;
const int MAXK = 19;
int depth[MAXN];
int skok[MAXN][MAXK];
vector<int> g[MAXN];
int P[MAXN];
int ojc[MAXN];
ll ans[MAXN];

int find(int v) {
    int pom = v;
    while (ojc[pom] != pom) {
        pom = ojc[pom];
    }
    while (ojc[v] != v) {
        int pam = ojc[v];
        ojc[v] = pom;
        v = pam;
    }
    return v;
}

void dfs(int v, int last) {
    depth[v] = depth[last] + 1;
    skok[v][0] = last;
    for (int k = 1; k < MAXK; k++) {
        skok[v][k] = skok[skok[v][k - 1]][k - 1];
    }
    for (auto syn: g[v]) {
        if (syn == last) continue;
        dfs(syn, v);
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    int k = MAXK - 1;
    while (depth[a] < depth[b]) {
        if ((depth[b] - (1 << k)) < depth[a]) {
            
        }
        else {
            b = skok[b][k];
        }
        k--;
    }
    if (a == b) {
        return a;
    }
    k = MAXK - 1;
    while (skok[a][0] != skok[b][0]) {
        if (skok[a][k] != skok[b][k]) {
            a = skok[a][k];
            b = skok[b][k];
        }
        k--;
    }
    return skok[a][0];
}

void solve() {
    rep(i, MAXN) {
        ojc[i] = i;
    }
	int n;
    cin >> n;
    pair<int, int> T[n];
    rep(i, n) {
        int p;
        cin >> p;
        P[i + 1] = p;
        T[i] = {p, i + 1};
    }
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1, 1);
    sort(T, T + n);
    ll odp = 0;
    rep(i, n) {
        int v = T[i].nd;
        for (auto syn: g[v]) {
            if (P[syn] < P[v]) {
                int w = find(syn);
                ll odl = depth[w] + depth[v] - 2 * depth[lca(w, v)];
                ans[v] = max(ans[v], odl + ans[w]);
                ojc[w] = v;
            }
        }
        odp = max(odp, ans[v]);
    }
    cout << odp << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
	return 0;
}

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