Submission #840081

#	Time	Username	Problem	Language	Result	Execution time	Memory
840081		dong_liu	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	210 ms	45432 KiB

Main

#include "bits/stdc++.h"
using namespace std;

const int N=2e5, L=18;

#ifndef LOCAL
#define cerr if(0)cerr
#endif

int n,p[N];
int pp[L][N],d[N];
vector<int>g[N];
long long dp[N];
int f[N];

int uf(int i) { return f[i]==i?i:f[i]=uf(f[i]); }

void dfs(int i){
	for(int l=1;l<L;l++)pp[l][i]=pp[l-1][pp[l-1][i]];
	for(int j:g[i])if(pp[0][i]!=j){
		pp[0][j]=i;
		d[j]=d[i]+1;
		dfs(j);
	}
}
int lca(int i,int j){
	if(d[i]<d[j])swap(i,j);
	int k=d[i]-d[j];
	for(int l=0;l<L;l++)if(k>>l&1)i=pp[l][i];
	if(i==j)return i;
	for(int l=L-1;l>=0;l--)if(pp[l][i]!=pp[l][j])i=pp[l][i],j=pp[l][j];
	return pp[0][i];
}
int dis(int i,int j){return d[i]+d[j]-2*d[lca(i,j)];}

int main() {
	cin.tie(0)->sync_with_stdio(0),cin.exceptions(cin.failbit);
	cin>>n;
	for(int i=0;i<n;i++)cin>>p[i],p[i]--;
	for(int h=0;h<n-1;h++){
		int i,j;cin>>i>>j,i--,j--;
		i=p[i],j=p[j];
		cerr<<"edge "<<i<<" "<<j<<endl;
		g[i].push_back(j);
		g[j].push_back(i);
	}
	pp[0][0]=0;
	dfs(0);
	for(int i=0;i<n;i++)f[i]=i;
	for(int i=0;i<n;i++){
		for(int j:g[i])if(j<i){
			int c=uf(j);
			cerr<<c<<" "<<i<<"|"<<dis(c,i)<<endl;
			dp[i]=max(dp[i],dp[c]+dis(c,i));
			f[c]=i;
		}
		cerr<<"dp["<<i<<"]="<<dp[i]<<endl;
	}
	cout<<*max_element(dp,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