// Problem URL: https://oj.uz/problem/view/JOI23_ho_t4
// Start Time: 5/27/2025, 9:44:51 PM
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int i = a; i < b; i++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define max(a,b) max<ll>(a,b)
#define min(a,b) min<ll>(a,b)
const int nmax = 2e5+3;
const int LOG = 32-__builtin_clz(nmax);
vector<int> adj[nmax];
int p[nmax], pos[nmax];
int n;
int t[2*nmax]; // promeni u sparse table jer nema update
void build(){for(int x = n-1; x>0; x--)t[x]=max(t[2*x],t[2*x+1]);}
void update(int i,int v){for(t[i+=n]=v;i>1;i>>=1)t[i>>1]=max(t[i],t[i^1]);}
int get (int l, int r){
int res = -1;
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
if(l&1)res=max(res,t[l++]);
if(r&1)res=max(res,t[--r]);
}
return res;
}
int timer = -1;
int dep[nmax], dt[nmax], ft[nmax], jmp[nmax][LOG+1];
void dfs(int u, int par=-1){
dt[u]=++timer;
for(int v : adj[u]){
if(v==par)continue;
jmp[v][0]=u;
dep[v]=dep[u]+1;
dfs(v,u);
}
ft[u]=timer;
}
void prec_lca(){
for(int j = 1; j<=LOG; j++){
for(int i = 1; i<=n; i++){
jmp[i][j] = jmp[jmp[i][j-1]][j-1];
}
}
}
int lca(int a, int b){
if(dep[a]<dep[b])swap(a,b);
//podigni a na istu visinu kao b
int dif = dep[a]-dep[b];
for(int i = 0; i<=LOG; i++){
if(dif&(1<<i)){
a = jmp[a][i];
}
}
if(a==b)return a;
for(int i = LOG; i>=0; i--){
if(jmp[a][i] != jmp[b][i]){
a = jmp[a][i];
b = jmp[b][i];
}
}
return jmp[a][0];
}
bool obst[nmax];
ll maxmoves(int mn){
ll res = 0;
obst[mn]=1;
update(dt[mn],-1);
// prvo odradi sva podstabla
for(int v : adj[mn]){
if(v==jmp[mn][0]) continue;//?
int maxv = get(dt[v],ft[v]+1);
if(maxv==-1)continue;
int maxnode = pos[maxv];
res = max(res, maxmoves(maxnode) + (dep[maxnode] - dep[mn]));
// ocrni celo podstablo
// zameni sa lazy kasnije
if(p[mn]==n) continue;
li(i,dt[maxnode],ft[maxnode]+1){
t[i+n]=-1;
}
build();
}
// nadji poslednjeg ne blokiranog pretka
if(p[mn]!=n){
int maxv = mn;
while(!obst[jmp[maxv][0]])maxv=jmp[maxv][0];
if(maxv != mn){
maxv = get(dt[maxv],ft[maxv]+1);
if(maxv!=-1){
int maxnode = pos[maxv];
res = max(res,maxmoves(maxnode) + dep[maxnode] + dep[mn] - 2*dep[lca(maxnode,mn)]);
}
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin>>n;
li(i,1,n+1){
cin>>p[i];
pos[p[i]]=i;
}
li(i,0,n-1){
int a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(pos[n]);
li(i,1,n+1) t[dt[i]+n]=p[i];
build();
prec_lca();
cout<<maxmoves(pos[n]);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |