#include <bits/stdc++.h>
using namespace std;
const long long N = 200001;
vector<long long> adj[N];
vector<long long> depth(N);
long long parents[N][18];
vector<long long> parent(N);
vector<long long> maxVal(N);
vector<long long> h(N);
vector<long long> sz(N);
void dfs(long long u, long long p){
for(long long v : adj[u]){
if(v != p){
parents[v][0] = u;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
}
long long distance(long long a, long long b){
long long dist = depth[a] + depth[b];
if(depth[a] < depth[b]){
swap(a, b);
}
long long diff = depth[a] - depth[b];
long long val = 0;
while(diff > 0){
if(diff & 1){
a = parents[a][val];
}
diff /= 2;
val++;
}
if(a == b){
return dist - 2 * depth[a];
}
for(long long i = 16; i >= 0; i++){
if(parents[a][i] != parents[b][i]){
a = parents[a][i];
b = parents[b][i];
}
}
return dist - 2 * depth[a] + 2;
}
long long getRoot(long long u){
if(parent[u] == u){
return u;
}
return parent[u] = getRoot(parent[u]);
}
void unite(long long a, long long b){
long long u = getRoot(a);
long long v = getRoot(b);
if(u == v){
return;
}
if(sz[u] == sz[v]){
sz[u]++;
}
if(sz[u] > sz[v]){
parent[v] = u;
if(h[maxVal[v]] > h[maxVal[u]]){
maxVal[u] = maxVal[v];
}
}
else{
parent[u] = v;
if(h[maxVal[u]] > h[maxVal[v]]){
maxVal[v] = maxVal[u];
}
}
}
int main(){
long long n;
cin >> n;
for(long long i = 1; i <= n; i++){
cin >> h[i];
}
for(long long i = 0; i < n - 1; i++){
long long a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
parents[1][0] = 1;
dfs(1, 0);
for(long long j = 1; j <= 18; j++){
for(long long i = 1; i <= n; i++){
parents[i][j] = parents[parents[i][j - 1]][j - 1];
}
}
for(long long i = 1; i <= n; i++){
parent[i] = i;
maxVal[i] = i;
}
vector<pair<long long, long long> > adj2[1 + n];
vector<pair<long long, long long> > positions(1 + n);
for(long long i = 1; i <= n; i++){
positions[i] = make_pair(h[i], i);
}
sort(positions.begin(), positions.end());
for(long long i = 1; i <= n; i++){
long long u = positions[i].second;
for(long long v : adj[u]){
if(h[v] <= h[u]){
long long weight = maxVal[getRoot(v)];
adj2[u].push_back(make_pair(weight, distance(u, weight)));
unite(u, v);
}
}
}
vector<long long> dist(1 + n);
vector<bool> visited(1 + n, false);
queue<long long> q;
q.push(positions[n].second);
while(!q.empty()){
long long u = q.front();
q.pop();
visited[u] = true;
for(pair<long long, long long> x : adj2[u]){
long long v = x.first;
if(!visited[v]){
visited[v] = true;
dist[v] = dist[u] + x.second;
q.push(v);
}
}
}
long long ans = 0;
for(long long i = 1; i <= n; i++){
ans = max(ans, dist[i]);
}
cout << ans << "\n";
}
Compilation message
Main.cpp: In function 'long long int distance(long long int, long long int)':
Main.cpp:37:5: warning: iteration 9223372036854775791 invokes undefined behavior [-Waggressive-loop-optimizations]
37 | for(long long i = 16; i >= 0; i++){
| ^~~
Main.cpp:37:29: note: within this loop
37 | for(long long i = 16; i >= 0; i++){
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
14168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
14168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
14168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
14168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
14168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2043 ms |
14168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
14168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
