Submission #1067514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067514		_rain_	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	199 ms	68280 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define debug false
#define int long long
const int maxn = 2e5;
const int maxlog = 20;
vector<int> g[maxn+2];
int dp[maxn+2] , p[maxn+2] , n , dep[maxn+2] , par[maxn+2][maxlog+2];

void dfs(int u , int p){
	par[u][0] = p;
	dep[u] = dep[p] + 1;
	for (int i = 1; i <= maxlog; ++i){
		par[u][i] = par[par[u][i - 1]][i - 1];
	}
	for (auto& v : g[u]){
		if (v==p) continue;
		dfs(v,u);
	}
	return;
}
int lca(int u , int v){
	if (dep[u] < dep[v]) swap(u,v);
	for (int i = maxlog; i >= 0; --i)
		if (dep[par[u][i]] >= dep[v]) u = par[u][i];
	if (u==v) return u;
	for (int i = maxlog; i >= 0; --i)
		if (par[u][i] != par[v][i]) u = par[u][i] , v = par[v][i];
	return par[u][0];
}
int dist(int u , int v){
	return dep[u] + dep[v] - 2 * dep[lca(u,v)];
}

int f[maxn+2] , sz[maxn+2] , mx[maxn+2];
int find(int u){
	return u == f[u] ? f[u] : f[u] = find(f[u]);
}
void unite(int u, int v){
	u = find(u); v = find(v);
	if (u==v) return ;
	if (sz[u] < sz[v]) swap(u,v);
	mx[u] = max(mx[u] , mx[v]);
	f[v] = u; sz[u] += sz[v];
	return;
}

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i) sz[i] = 1 , f[i] = i , mx[i] = i;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	for (int i = 1; i < n; ++i){
		int u , v; cin >> u >> v;
		g[p[u]].push_back(p[v]);
		g[p[v]].push_back(p[u]);
	}
	dfs(n,0);
	for (int i = 1; i <= n; ++i){
		for (auto& v : g[i]){
			int x = mx[find(v)];
			if (x < i){
				dp[i] = max(dp[i] , dp[x] + dist(x , i));
				unite(x,i);
			}
		}
	}
	cout << dp[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