Submission #1022517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022517		Aiperiii	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	312 ms	79192 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=2e5+5;
int a[N],d[N],p[N],dp[N];
vector <int> g[N],g2[N];
int jmp[20][N];

void dfs(int v,int p){
    jmp[0][v]=p;
    for(auto to : g[v]){
        if(to!=p){
            d[to]=d[v]+1;
            dfs(to,v);
        }
    }
}

int lca(int v,int u){
    if(d[v]<d[u])swap(u,v);
    for(int k=19;k>=0;k--){
        if(d[jmp[k][v]]>=d[u]){
            v=jmp[k][v];
        }
    }
    if(u==v)return v;
    for(int k=19;k>=0;k--){
        if(jmp[k][v]!=jmp[k][u]){
            v=jmp[k][v];
            u=jmp[k][u];
        }
    }
    return jmp[0][v];
}
int find_set(int v){
    if(p[v]==v)return v;
    return p[v]=find_set(p[v]);
}
void union_set(int v,int u){
    u=find_set(u);
    p[u]=v;
    g2[v].pb(u);
}

int dist(int v,int u){
    int l=lca(u,v);
    return d[u]+d[v]-2*d[l];
}
void dfs2(int v,int p){
    for(auto to : g2[v]){
        if(to!=p){
            dfs2(to,v);
            dp[v]=max(dp[to]+dist(to,v),dp[v]);
        }
    }
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=i;
    }
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        g[a[u]].pb(a[v]);
        g[a[v]].pb(a[u]);
    }
    
    dfs(n,n);
    
    for(int k=1;k<20;k++){
        for(int i=1;i<=n;i++){
            jmp[k][i]=jmp[k-1][jmp[k-1][i]];
        }
    }
    
    for(int i=2;i<=n;i++){
        for(auto to : g[i]){
            if(to<i){
                union_set(i,to);
            }
        }
    }
    
    dfs2(n,0);
    cout<<dp[n]<<"\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