#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSUF{
vector<ll> P;
ll fs(ll node){
if(P[node]==node) return node;
return P[node]=fs(P[node]);
}
void us(ll a, ll b){
a=fs(a);b=fs(b);
if(a!=b) P[b]=a;
}
DSUF(ll n){
P.assign(n+5,0);
for(int i=0; i<P.size(); i++)
P[i]=i;
}
};
vector<ll> g[200001], v(200001,0),G[200001];
ll bl[22][200001];
void dfs(ll node)
{
for(int j=1; j<22; j++)
bl[j][node]=bl[j-1][bl[j-1][node]];
for(auto i:G[node])
if(v[i]==0){
v[i]=v[node]+1;
bl[0][i]=node;
dfs(i);
}
}
ll cost(ll a, ll b)
{
if(v[a]<v[b])
swap(a,b);
ll cost=v[a]-v[b];
for(int i=21; i>-1; i--)
if((cost&(1<<i))!=0)
a=bl[i][a];
for(int i=21; i>-1; i--)
{
if(bl[i][a]!=bl[i][b])
{
a=bl[i][a];
b=bl[i][b];
cost+=(1<<i)*2;
}
}
if(a!=b) cost+=2;
return cost;
}
struct LowerCommonAncestor
{
vector <int> L, E, H; int idx, n;
void dfs(int cur, int depth, int parent)
{
H[cur] = idx;
E[idx] = cur;
L[idx++] = depth;
for (auto& u : G[cur]) if(u != parent)
{
dfs(u, depth + 1, cur);
E[idx] = cur;
L[idx++] = depth;
}
}
vector <int> tree; int l;
int query(int node, int x, int y, int s, int e)
{
if (x > e || y < s) return 0;
if (s >= x && e <= y)
return tree[node];
int middle = (s + e) / 2;
int id1 = query(node * 2, x, y, s, middle),
id2 = query(node * 2 + 1, x, y, middle + 1, e);
return (L[id1] > L[id2] ? id2 : id1);
}
int query(int i, int j) { return query(1, i, j, 1, l); }
void Segment_tree(int n)
{
for (l = 1; l < n; l = (l << 1));
tree.assign(2 * l, 0); L[0] = Inf;
for (int i = 0; i < n; i++)
tree[i + l] = i + 1;
for (int i = l - 1; i > 0; i--)
{
tree[i] = (L[tree[2 * i]] > L[tree[2 * i + 1]] ?
tree[2 * i + 1] : tree[2 * i]);
}
}
int Ancestor(int i, int j)
{
int a = min(H[i], H[j]), b = max(H[i], H[j]);
return E[query(a, b)];
}
int Dist(int x)
{
return L[H[x]];
}
int sol(int i, int j)
{
int g = Ancestor(i, j);
return (Dist(i) + Dist(j) - (2 * Dist(g)));
}
LowerCommonAncestor(int lenght, int x)
{
n = lenght; idx = 1;
L.assign(2 * n, -1);
E.assign(2 * n, -1);
H.assign(2 * n, -1);
dfs(x, 0, 0); Segment_tree(2*n-2); //RMQ();
}
};
int main()
{
ll n;
cin>>n;
pair<ll,ll> cad[n];
DSUF asd(n+2);
for(int i=0; i<n; i++)
{
cin>>cad[i].first;
cad[i].second=i+1;
}
for(int i=0; i<n-1; i++)
{
ll a,b;
cin>>a>>b;
if(cad[a-1].first<cad[b-1].first) swap(a,b);
g[a].push_back(b);
G[a].push_back(b);
G[b].push_back(a);
}
LowerCommonAncestor D(n, 1);
sort(cad,cad+n);
ll sol[n+2]={ };
for(int i=0; i<n; i++)
{
pair<ll,ll> temp=cad[i];
for(auto i:g[temp.second])
{
sol[temp.second]=max(sol[temp.second],sol[asd.fs(i)]+D.sol(temp.second,asd.fs(i)));
asd.us(temp.second,i);
}
}
cout<<sol[cad[n-1].second];
}
Compilation message
Main.cpp: In constructor 'DSUF::DSUF(ll)':
Main.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=0; i<P.size(); i++)
| ~^~~~~~~~~
Main.cpp: In member function 'void LowerCommonAncestor::Segment_tree(int)':
Main.cpp:95:39: error: 'Inf' was not declared in this scope; did you mean 'ynf'?
95 | tree.assign(2 * l, 0); L[0] = Inf;
| ^~~
| ynf
