This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 18;
int up[N][K], tin[N], tout[N], timer, dep[N];
int n, a[N], vis[N];
vector<int> g[N];
bool anc(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
void dfs(int v, int p) {
up[v][0] = p;
tin[v] = ++timer;
dep[v] = dep[p] + 1;
for (int i = 1;i < K;i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto u : g[v]) {
if (u == p)
continue;
dfs(u, v);
}
tout[v] = timer;
}
int Lca(int a, int b) {
if (anc(a, b))
return a;
else if (anc(b, a))
return b;
for (int i = K - 1;i >= 0;i--) {
if (!anc(up[a][i], b) && up[a][i] > 0)
a = up[a][i];
}
return up[a][0];
}
int distance(int a, int b) {
int lc = Lca(a, b);
return dep[a] + dep[b] - 2 * dep[lc];
}
pair<int, int> find_mx(int v, int p) {
if (vis[v])
return {0, 0};
int mx = a[v], s = v;
for (auto u : g[v]) {
if (u == p)
continue;
auto x = find_mx(u, v);
if (x.f > mx) {
mx = x.f;
s = x.s;
}
}
return {mx, s};
}
int solve(int x, int p) {
int v = find_mx(x, 0).s;
vis[v] = 1;
int res = 0;
for (auto u : g[v]) {
if (u == p || vis[u])
continue;
res = max(res, solve(u, v));
}
return res + distance(v, p);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n;
for (int i = 1;i <= n;i++)
cin >> a[i];
for (int i = 1;i <= n - 1;i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
int mx = 1;
for (int i = 2;i <= n;i++) {
if (a[i] > a[mx])
mx = i;
}
dfs(1, 0);
cout << solve(mx, mx) << '\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... |