This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> sz, p;
vector<pair<int, int>> mx;
DSU(int _n, vector<int> vals) {
n = _n;
sz.assign(n, 1);
p.resize(n);
iota(p.begin(), p.end(), 0);
mx.resize(n);
for (int i = 0; i < n; ++i) {
mx[i] = {vals[i], i};
}
}
int pr(int v) {
if (p[v] == v) {
return v;
}
return p[v] = pr(p[v]);
}
void unite(int a, int b) {
a = pr(a), b = pr(b);
if (a == b) {
return;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
p[b] = a;
sz[a] += sz[b];
mx[a] = max(mx[a], mx[b]);
}
};
constexpr int maxn = 2e5 + 5, lg = 20;
vector<int> g[maxn];
int go[lg][maxn];
int tin[maxn], tout[maxn];
int t = 0;
int d[maxn];
void dfs(int v) {
tin[v] = t;
t++;
for (auto u : g[v]) {
if (u != go[0][v]) {
go[0][u] = v;
d[u] = d[v] + 1;
dfs(u);
}
}
tout[v] = t;
}
int lca(int a, int b) {
if (tin[a] <= tin[b] && tout[b] <= tout[a]) {
return a;
}
if (tin[b] <= tin[a] && tout[a] <= tout[b]) {
return b;
}
int v = a;
for (int i = lg - 1; i >= 0; --i) {
if (!(tin[go[i][v]] <= tin[b] && tout[b] <= tout[go[i][v]])) {
v = go[i][v];
}
}
return go[0][v];
}
int get_dist(int a, int b) {
return d[a] + d[b] - d[lca(a, b)] * 2;
}
void solve() {
int n;
cin >> n;
vector<int> p(n);
vector<pair<int, int>> ord(n);
for (int i = 0; i < n; ++i) {
cin >> p[i];
p[i]--;
ord[i] = {p[i], i};
}
sort(ord.begin(), ord.end());
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0);
for (int i = 1; i < lg; ++i) {
for (int j = 0; j < n; ++j) {
go[i][j] = go[i - 1][go[i - 1][j]];
}
}
vector<long long> dp(n);
vector<vector<int>> updates(n);
DSU d(n, p);
for (int i = 0; i < n; ++i) {
for (auto j : g[ord[i].second]) {
if (p[j] < ord[i].first) {
updates[i].push_back(d.mx[d.pr(j)].first);
d.unite(ord[i].second, j);
}
}
}
long long ans = 0;
for (int i = n - 1; i >= 0; --i) {
for (auto j : updates[i]) {
dp[j] = max(dp[j], dp[i] + get_dist(ord[i].second, ord[j].second));
ans = max(ans, dp[j]);
}
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
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... |