제출 #1236042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236042		wetsponge	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	258 ms	62908 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define mod 1000000007
const int N=(1ll<<20);
int n,lv[200001],t[21][200001],arr[200001],ans[200001];
vector <int> v[200001];
void solve(int i,int last){
    t[0][i]=last;
    lv[i]=lv[last]+1;
    for(int j:v[i]){
        if(j==last) continue;
        solve(j,i);
    }
    return;
}
int LCA(int a,int b){
    if(lv[a]<lv[b]) swap(a,b);
    int k=lv[a]-lv[b];
    for(int bt=20;bt>=0;bt--){
        if(k>=(1<<bt)){
            a=t[bt][a];
            k-=(1<<bt);
        }
    }
    if(a==b) return a;
    for(int bt=20;bt>=0;bt--){
        if(t[bt][a]!=t[bt][b]){
            a=t[bt][a];
            b=t[bt][b];
        }
    }
    return t[0][a];
}
int dis(int a,int b){
    return lv[a]+lv[b]-lv[LCA(a,b)]*2;
}
int parent[200001];
int find(int i){
    if(parent[i]==i) return i;
    return parent[i]=find(parent[i]);
}
void merge(int a,int b){
    a=find(a),b=find(b);
    parent[b]=a;
    return;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    vector <array<int,2>> qu;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        parent[i]=i;
        qu.push_back({arr[i],i});
    }
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    solve(1,0);
    for(int bt=1;bt<=20;bt++){
        for(int i=1;i<=n;i++) t[bt][i]=t[bt-1][t[bt-1][i]];
    }
    sort(qu.begin(),qu.end());
    for(auto [val,i]:qu){
        for(int j:v[i]){
            if(arr[j]>arr[i]) continue;
            ans[i]=max(ans[i],ans[find(j)]+dis(find(j),i));
            merge(i,j);
        }
    }
    cout<<ans[find(1)]<<endl;
}
//179276892

• 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