Submission #937825

#	Time	Username	Problem	Language	Result	Execution time	Memory
937825		tianyaochiun	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	403 ms	72692 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define pii pair<long long,long long> 
#define F first
#define S second
#define pb emplace_back
#define endl "\n"
#define all(a) a.begin(),a.end()
#define int long long

vector<int> p;

struct DSU{
	vector<int> rt,sz,mx;
	DSU(int _n){
		rt.resize(_n+1);
		sz.assign(_n+1,1);
		mx.resize(_n+1);
		iota(all(rt),0);
		iota(all(mx),0);
	}
	int find(int i){
		if(rt[i]==i) return i;
		return rt[i]=find(rt[i]);
	}
	void un(int u,int v){
		u=find(u),v=find(v);
		if(u==v) return;
		if(sz[u]>sz[v]) swap(u,v);
		rt[u]=v;
		sz[v]+=sz[u];
		mx[v]=p[mx[u]]>p[mx[v]]?mx[u]:mx[v];
	}
};

void solve(){
	int n;
	cin>>n;
	p.resize(n+1);
	vector<int> pa(n+1),dep(n+1),idx(n+1),dp(n+1);
	vector<bool> vis(n+1);
	vector<vector<int>> g(n+1);
	for(int i=1;i<=n;i++){
		cin>>p[i];
		idx[p[i]]=i;
	} 
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	auto dfs=[&](auto dfs,int i,int pre)->void{
		dep[i]=dep[pre]+1;
		pa[i]=pre;
		for(int j:g[i]){
			if(j==pre) continue;
			dfs(dfs,j,i);
		}
	};
	dfs(dfs,1,1);
	vector<vector<int>> table(n+1,vector<int>(19));
	for(int i=1;i<=n;i++) table[i][0]=pa[i];
	for(int i=1;i<19;i++){
		for(int j=1;j<=n;j++){
			table[j][i]=table[table[j][i-1]][i-1];
		}
	}
	auto lca=[&](int u,int v){
		if(dep[u]>dep[v]) swap(u,v);
		for(int i=18;i>=0;i--){
			if(dep[table[v][i]]>=dep[u]) v=table[v][i];
		}
		if(u==v) return u;
		for(int i=18;i>=0;i--){
			if(table[u][i]!=table[v][i]){
				u=table[u][i];
				v=table[v][i];
			}
		}
		return table[u][0];
	};
	DSU dsu(n);
	for(int i=1;i<=n;i++){
		vis[idx[i]]=1;
		for(int j:g[idx[i]]){
			if(vis[j]){
				int node=dsu.mx[dsu.find(j)];
				dp[idx[i]]=max(dp[idx[i]],dp[node]+dep[idx[i]]+dep[node]-2*dep[lca(idx[i],node)]);
				dsu.un(idx[i],j);
			}
		}
	}
	cout<<dp[idx[n]];
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(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