Submission #1158492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158492		ReLice	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	166 ms	75016 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll N = 2e5 + 8;

vector<vector<ll>> g(N), ng(N);
ll siz[N], p[N], mx[N];
ll up[N][20], d[N];

ll anc(ll a){ return (p[a] == a ? a : anc(p[a])); }

bool uni(ll a, ll b){
    a = anc(a), b = anc(b);

    if(a == b) return false;
    if(siz[a] > siz[b]) swap(a, b);

    p[a] = b;
    siz[b] += siz[a];
    mx[b] = max(mx[a], mx[b]);

    return true;
}

void dfs(ll v){

    for(ll i=1;i<=19;i++) up[v][i] = up[up[v][i - 1]][i - 1];

    for(auto i : g[v]){
        if(i == up[v][0]) continue;

        d[i] = d[v] + 1;
        up[i][0] = v;

        dfs(i);
    }
}

ll lca(ll a, ll b){
    if(d[a] < d[b]) swap(a, b);

    for(ll i=19;i>=0;i--){
        if(d[a] - d[b] >= (1<<i)){
            a = up[a][i];
        }
    }

    if(a == b) return a;

    for(ll i=19;i>=0;i--){
        if(up[a][i] != up[b][i]){
            a = up[a][i];
            b = up[b][i];
        }
    }

    return up[a][0];
}

ll dis(ll a, ll b){
    return d[a] + d[b] - 2 * d[lca(a, b)];
}

void solve() {
    ll i, j;

    ll n;
    cin>>n;

    ll v[n + 1];
    for(i=1;i<=n;i++) {
        cin>>v[i];
        p[i] = i;
        siz[i] = 1;
        mx[i] = i;
    }

    for(i=1;i<n;i++){
        ll a, b;
        cin>>a>>b;

        a = v[a];
        b = v[b];

        g[a].pb(b);
        g[b].pb(a);
    }

    for(i=1;i<=n;i++){
        for(auto to : g[i]){
            if(to < i){
                ng[i].pb(mx[anc(to)]);
                //cout<<i<<' '<<mx[anc(to)]<<endl;
                uni(i, to);
            }
        }
    }

    d[1] = 0;
    up[1][0] = 1;
    dfs(1);

    vector<ll> ans(n + 1, 0);
    ll mx = 0;

    for(i=n;i>0;i--){
        mx = max(mx, ans[i]);
        //cout<<ans[i]<<endl;
        for(auto to : ng[i]){
            //cout<<i<<' '<<to<<' '<<dis(to, i)<<endl;
            ans[to] = ans[i] + dis(to, i);
        }
    }

    cout<<mx<<endl;
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) 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