#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;
}
int 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];
}
Compilation message
cc1plus: error: '::main' must return 'int'
