Submission #1042879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042879		SoulKnight	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	184 ms	43932 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, a[N], par[N], dep[N], up[LG][N];
ll dp[N];
vector<int> adj[N];

void dfs(int u, int p){
    dep[u] = 1 + dep[p];

    up[0][u] = p;
    for (int i = 1; i < LG; i++) up[i][u] = up[i-1][up[i-1][u]];

    for (auto v: adj[u]){
        if (v == p) continue;
        dfs(v, u);
    }
}

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

    for (int i = LG-1; i >= 0; i--) if (dep[up[i][u]] >= dep[v]) u = up[i][u];
    if (u == v) return u;

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

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

int find(int u) {return u == par[u]? u: par[u]=find(par[u]);}






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

    for (int i = 1; i <= n; i++){
        for (auto v: adj[i]){
            v = find(v);
            if (v < i) {
                par[v] = i;
                dp[i] = max(dp[i], dist(i, v) + dp[v]);
            }
        }
    }
    cout << dp[n] << 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: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26