#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
typedef vector < int > vint;
const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;
const int lg = 20;
vector < vint > adj(mxn);
int n;
int a[mxn] , p[mxn];
int lev[mxn] , tab[lg][mxn];
int in[mxn] , out[mxn];
int rev[mxn];
int timer = 0;
void tour(int u , int par) {
in[u] = ++timer;
a[timer] = p[u];
rev[timer] = u;
for (int v : adj[u]) {
if (v == par) continue;
tour(v , u);
}
out[u] = timer;
}
struct node {
int tl , tm , tr;
int id;
bool lz;
node *left , *right;
node (int l , int r) {
tl = l , tr = r , tm = (l + r) / 2;
lz = 0;
if (tl == tr) {
id = tl;
return;
}
left = new node(tl , tm);
right = new node(tm+1 , tr);
id = (a[left->id] > a[right->id]) ? left->id : right->id;
}
int querrrry(int l , int r) {
if (tl == l && tr == r) return id;
if (r <= tm) return left -> querrrry(l , r);
else if (l > tm) return right -> querrrry(l , r);
int idl = left -> querrrry(l , tm);
int idr = right -> querrrry(tm+1 , r);
return (a[idl] > a[idr]) ? idl : idr;
}
int query(int l , int r) {
return rev[querrrry(l , r)];
}
void pro() {
if (lz == 0) return;
left -> lz = right -> lz = 1;
left -> id = right -> id = 0;
lz = 0;
}
void update(int l , int r) {
if (tl == l && tr == r) {
lz = 1;
id = 0;
return;
}
pro();
if (r <= tm) left -> update(l , r);
else if (l > tm) right -> update(l , r);
else {
left -> update(l , tm);
right -> update(tm+1 , r);
}
id = (a[left->id] > a[right->id]) ? left->id : right->id;
}
} *root;
void setlev(int u , int par , int lv) {
lev[u] = lv;
tab[0][u] = par;
for (int v : adj[u]) {
if (v == par) continue;
setlev(v , u , lv+1);
}
}
void build(int st) {
setlev(st , st , 0);
for (int i = 1; i < lg; i++) {
for (int j = 1; j <= n; j++) {
tab[i][j] = tab[i-1][tab[i-1][j]];
}
}
}
int dis(int a , int b) {
if (lev[b] < lev[a]) swap(a , b);
int d = lev[b] - lev[a];
for (int i = 0; i < lg; i++) {
if (d & (1 << i)) b = tab[i][b];
}
if (a == b) return d;
int ret = 0;
for (int i = lg-1; i >= 0; i--) {
if (tab[i][a] != tab[i][b]) {
a = tab[i][a];
b = tab[i][b];
ret += (1 << i);
}
}
return (ret + 1) * 2 + d;
}
int dfs(int u) {
int ver = root -> query(in[u] , out[u]);
if (ver == u) {
root -> update(in[u] , in[u]);
ver = root -> query(in[u] , out[u]);
if (ver == 0) return 0;
int result = 0;
for (int v : adj[u]) {
if (lev[v] < lev[u]) continue;
result = max(result , dfs(v) + 1);
}
root -> update(in[u] , out[u]);
return result;
}
// cout << u << ' ' << ver << '\n';
if (ver == 0) return 0;
// cout << "CONTINUING " << u << ' ' << ver << '\n';
root -> update(in[ver] , in[ver]);
int ans = dfs(ver) + dis(u , ver);
root -> update(in[ver] , out[ver]);
// cout << "current answer is: " << ans << '\n';
int ret = dis(u , ver);
while (1) {
int newver = root -> query(in[u] , out[u]);
// cout << "CURRENTLY AT u = " << u << " BUT NEWVER IS: " << newver << '\n';
if (newver == 0) break;
ret += dis(ver , newver);
// cout << "RET: " << ret << '\n';
ver = newver;
// root -> update(in[ver] , in[ver]);
ans = max(ans , ret + dfs(ver));
root -> update(in[ver] , out[ver]);
// cout << "current answer is: " << ans << '\n';
}
return ans;
}
signed main() {
cin >> n;
int st = 1;
for (int i = 1; i <= n; i++) {
cin >> p[i];
if (p[i] == n) st = i;
}
for (int i = 0; i < n-1; i++) {
int v , u;
cin >> v >> u;
adj[u].push_back(v);
adj[v].push_back(u);
}
build(st);
tour(st , st);
a[0] = -inf;
// cout << "GOBRRR";
// for (int i = 0; i <= n; i++) cout << a[i] << ' ';
// cout << '\n';
root = new node(0 , n);
// cout << dfs(1) << '\n';
// int answer = 0;
// for (int v : adj[st]) {
// int tempor = dfs(v);
// answer = max(answer , 1 + tempor);
// // cout << "Answer for node " << v << " is " << 1 + tempor << '\n';
// }
cout << dfs(st) << '\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... |