Submission #860693

#	Time	Username	Problem	Language	Result	Execution time	Memory
860693		epicci23	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	323 ms	88556 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 2e5 + 10;
const int LOG = 20;

int lift[N][LOG];
int depth[N];
int ar[N];
vector<int> v[N];
vector<array<int,2>> v2[N];

void dfs(int c,int p,int d){
  depth[c]=d;
  lift[c][0]=p;
  for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];

  for(int x:v[c]){
  	if(x==p) continue;
  	dfs(x,c,d+1);
  }
}

int kth_par(int a,int x){
  for(int i=0;i<LOG;i++) if(x>>i&1) a=lift[a][i];
  return a;
}

int lca(int a,int b){
  if(depth[a]<depth[b]) swap(a,b);
  a=kth_par(a,depth[a]-depth[b]);
  if(a==b) return a;
  for(int i=LOG-1;i>=0;i--){
  	if(lift[a][i]!=lift[b][i]){
  	  a=lift[a][i];
  	  b=lift[b][i];
  	}
  }
  return lift[a][0];
}

int dist(int a,int b){
 return depth[a] + depth[b] - 2*depth[lca(a,b)];
}

int par[N];
int siz[N];
int val[N];

int find(int a){
  if(a==par[a]) return a;
  return par[a]=find(par[a]);
}

void merge(int a,int b){
  a=find(par[a]),b=find(par[b]);
  if(a==b) return;
 
  if(siz[a]>siz[b]) swap(a,b);

  siz[b]+=siz[a];
  par[a]=b;
  if(ar[val[a]]>ar[val[b]]) val[b]=val[a];
}

int dp[N];

void dfs2(int c,int p){
  for(auto x:v2[c]){
  	if(x[1]==p) continue;
  	dfs2(x[1],c);
    dp[c]=max(dp[c],x[0]+dp[x[1]]);
  }
 // cout << "c: " << c << " " << dp[c] << endl;
}

void solve(){
  int n;
  cin >> n;
  for(int i=1;i<=n;i++) cin >> ar[i];
  
  int xd[n+1];
  vector<int> act(n+1,0);
  for(int i=1;i<=n;i++) xd[ar[i]]=i;

  for(int i=1;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].pb(b);
  	v[b].pb(a);
  }
  
  for(int i=1;i<=n;i++){
  	val[i]=i;
  	siz[i]=1;
  	par[i]=i;
  }

  dfs(1,0,0);
   
  for(int i=1;i<=n;i++){
    int u = xd[i];
    act[u] = 1;
    for(int x:v[u]){
      if(!act[x]) continue;
      int w = val[find(x)];
      v2[u].pb({dist(u,w),w});
      v2[w].pb({dist(u,w),u});
      // cout << "new: " << u << " " << w << " " << dist(u,w) << endl; 
    }
    for(int x:v[u]){
      if(!act[x]) continue;
      merge(x,u);
    }
  }
  

  dfs2(xd[n],0); 

  cout << dp[xd[n]] << endl;

}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  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