#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define len(v) (int)((v).size())
template<typename T>
ostream& operator<<(ostream& out, const vector<T> &a){
for (auto& x : a){
out << x << ' ';
}
out << '\n';
return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &a){
for (size_t i = 0; i < a.size(); ++i){
in >> a[i];
}
return in;
}
mt19937 gen;
struct obj{
ll vl = -1e18, add = 0;
int i = -1;
obj() = default;
obj(int i, int x) : vl(x), i(i) {}
};
obj merge(obj &a, obj &b){
if (a.vl > b.vl){
return a;
}
else {
return b;
}
}
const int sz = 1 << 20;
obj tree[sz];
void push(int v, int ln){
if (tree[v].add == 0) return;
if (ln > 1){
tree[v * 2].add += tree[v].add;
tree[v * 2 + 1].add += tree[v].add;
}
tree[v].vl += tree[v].add;
tree[v].add = 0;
}
void upd(int v, int l, int r, int ql, int qr, int qx){
push(v, r - l);
if (l >= qr || ql >= r) return;
if (l >= ql && r <= qr) {
tree[v].add += qx;
push(v, r - l);
return;
}
int m = (l + r) / 2;
upd(v * 2, l, m, ql, qr, qx);
upd(v * 2 + 1, m, r, ql, qr, qx);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
obj sum(int v, int l, int r, int ql, int qr){
push(v, r - l);
if (l >= qr || ql >= r) return obj();
if (l >= ql && r <= qr) tree[v];
int m = (l + r) / 2;
obj r1 = sum(v * 2, l, m, ql, qr);
obj r2 = sum(v * 2 + 1, m, r, ql, qr);
return merge(r1, r2);
}
void build(int v, int l, int r, vector<int>& a){
if (r - l == 1){
tree[v] = obj(l, a[l]);
return;
}
int m = (l + r) / 2;
build(v * 2, l, m, a);
build(v * 2 + 1, m, r, a);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
const int N = 2e5 + 7;
vector<int> g[N];
int a[N];
bool us[N];
int tim = 0;
int tin[N], tout[N], p[N], h[N];
void dfs2(int v, int pre){
tin[v] = tim++;
p[v] = pre;
h[v] = h[pre] + 1;
for (int u : g[v]){
if (u == pre) continue;
dfs2(u, v);
}
tout[v] = tim;
}
const int LGN = 20;
int up[LGN][N];
int la(int v, int k){
for (int j = LGN - 1; j >= 0; --j){
if (k >= (1 << j)){
k -= (1 << j);
v = up[j][v];
}
}
return v;
}
int lca(int v, int u){
v = la(v, h[v] - h[u]);
u = la(u, h[u] - h[v]);
if (v == u) return v;
for (int j = LGN - 1; j >= 0; --j){
if (up[j][v] != up[j][u]){
v = up[j][v];
u = up[j][u];
}
}
return up[0][v];
}
int dist(int v, int u){
return h[v] + h[u] - 2 * h[lca(u, v)];
}
pair<int, int> dfs3(int v, int p){
pair<int, int> res = {v, 0};
for (int u : g[v]){
if (u == p) continue;
if (us[u]) continue;
pair<int, int> r = dfs3(u, v);
r.second++;
if (a[r.first] > a[res.first]) res = r;
}
return res;
}
int dfs(int v){
pair<int, int> cf = dfs3(v, v);
cf.second = dist(cf.first, v);
v = cf.first;
int res = 0;
us[v] = true;
for (int u : g[v]){
if (!us[u]){
res = max(res, dfs(u));
}
}
us[v] = false;
return res + cf.second + 1;
}
inline void solve() {
int n;
cin >> n;
for (int i = 0; i < n; ++i){
cin >> a[i];
us[i] = false;
}
for (int i = 0; i < n - 1; ++i){
int x, y;
cin >> x >> y;
g[--x].push_back(--y);
g[y].push_back(x);
}
dfs2(0, 0);
for (int i = 0; i < n; ++i){
up[0][i] = p[i];
}
for (int j = 1; j < LGN; ++j){
for (int i = 0; i < n; ++i){
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
vector<int> init(n);
for (int i = 0; i < n; ++i){
init[tin[i]] = a[i];
}
// build(1, 0, n, init);
int ans = 0;
for (int i = 0; i < n; ++i){
if (a[i] == n){
ans = dfs(i);
}
}
cout << ans - 1 << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout.precision(60);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
# | 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... |