제출 #871054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871054		Maite_Morale	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	542 ms	157372 KiB

Main

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>

struct ST{
    vll tree;ll sz;
    ST(ll _sz){
        sz=_sz*2;
        tree.assign(sz*2+100,0);
    }
    void update(ll a,ll b,ll x,ll y,ll n){
        if(x-y==0){tree[n]=b;return;}
        ll m=(x+y)/2;
        if(a<=m)update(a,b,x,m,n*2);
        else    update(a,b,m+1,y,n*2+1);
        tree[n]=max(tree[n*2],tree[n*2+1]);
    }
    ll query(ll a,ll b,ll x,ll y,ll n){
        if(y<a || x>b)return 0;
        if(a<=x && y<=b)return tree[n];
        ll m=(x+y)/2;
    return max(query(a,b,x,m,n*2),query(a,b,m+1,y,n*2+1));
    }
    void update(ll a,ll b){
        update(a,b,0,sz,1);
    }
    ll query(ll a,ll b){
        if(a>b)swap(a,b);
        return query(a,b,0,sz,1);
    }
} eu(MAX);
ll n,d[MAX],p[MAX],f[MAX],a[MAX],s[30][MAX],pass[MAX],c=0;
vll v[MAX];
void dfs(ll x,ll y){
    c++;eu.update(c,x);p[x]=c;
    d[x]=d[y]+1;s[0][x]=y;
    for(ll w : v[x]){
        if(w==y)continue;
        dfs(w,x);
    }
    f[x]=c;
}//4 3 1 2                     
ll lca(ll x,ll y){
   if(d[x]<d[y])swap(x,y);
   for(int i=20;i>=0;i--)if(d[x]-(1<<i)>=d[y])x=s[i][x];
   if(x==y)return y;
   for(int i=20;i>=0;i--)if(s[i][x]!=s[i][y]){x=s[i][x];y=s[i][y];}
return s[0][y];
}
ll dist(ll x,ll y){
    return d[x]+d[y]-2*d[lca(x,y)];
}
ll ans(ll x,ll y,ll z){//cout<<z<<" "<<x<<"-"<<y<<":";
    ll r=0;eu.update(p[z],-1);
    pass[z]=-1;
    for(int w: v[z]){
        if(pass[w]==-1 || s[0][z]==w)continue;
        ll mx=eu.query(p[w],f[w]);
       // cout<<mx<<" "<<p[w]<<" "<<f[w]<<"\n";
        if(mx<=0)continue;
        r=max(r,dist(z,mx)+ans(p[w],f[w],mx));
    }//cout<<"\n";
    ll mx=eu.query(x,y);//cout<<"mx:"<<mx<<"\n";
    if(mx<=0){/*cout<<r<<"\n";*/return r;}
    r=max(r,dist(z,mx)+ans(x,y,mx));
return r;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }ll a1,a2;
    for(int i=1;i<n;i++){
        cin>>a1>>a2;a1=a[a1];a2=a[a2];
        v[a1].push_back(a2);
        v[a2].push_back(a1);
    }dfs(n,n);
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            s[i][j]=s[i-1][s[i-1][j]];
        }
    }//cout<<-1<<"\n\n";
    cout<<ans(p[n],f[n],n);
return 0;
}

• 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