#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;
const int N = 2e5 + 7;
vector<int> g[N];
int a[N];
bool us[N];
int dfs2(int v, int p){
int res = v;
for (int u : g[v]){
if (u == p) continue;
if (us[u]) continue;
int r = dfs2(u, v);
if (a[r] > a[res]) res = r;
}
return res;
}
int dfs(int v){
v = dfs2(v, v);
int res = 0;
us[v] = true;
for (int u : g[v]){
if (!us[u]){
res = max(res, dfs(u));
}
}
us[v] = false;
return res + 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);
}
cout << dfs(0) << '\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... |