Submission #1092676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092676		Trisanu_Das	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	127 ms	41736 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;

int n;
int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
vector<int> adj[N];
long long dp[N];
 
void dfs(int u,int p = 0){
    pa[u] = p;
    sz[u] = 1;
    lv[u] = lv[p] + 1;
    for(auto v : adj[u]) 
        if(v != p){
            dfs(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[hv[u]])hv[u]=v;
        }
}
 
void hld(int u,int p=0){
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
    for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}
 
int lca(int u,int v){
    while(hd[u]!=hd[v]){
        if(lv[hd[u]]<lv[hd[v]])swap(u,v);
        u=pa[hd[u]];
    }
    return lv[u]<lv[v]?u:v;
}
 
int dist(int u,int v){
    return lv[u]+lv[v]-2*lv[lca(u,v)];
}
 
int fp(int u){
    return fa[u]=fa[u]==u?u:fp(fa[u]);
}
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1);
    hld(1);
    iota(fa+1,fa+n+1,1);
    iota(ord+1,ord+n+1,1);
    sort(ord+1,ord+n+1,[&](int i,int j){
        return a[i]<a[j];
    });
    for(int i=1;i<=n;i++){
        int u=ord[i];
        for(auto v:adj[u])if(a[u]>a[v]){
            v=fp(v);
            dp[u]=max(dp[u],dp[v]+dist(u,v));
            fa[v]=u;
        }
    }
    cout << dp[ord[n]];
}

• 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