#include <bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define lim 25
#define mid (start+end)/2
#define pb push_back
int n,l;
int dizi[lim],dp[lim][(1<<25)];
vector<int> v[lim];
int timer,tin[lim],tout[lim],dist[lim];
int up[lim][35],ger[lim][35];
inline void dfs(int node,int ata){
tin[node]=tout[node]=++timer;
dist[node]=dist[ata]+1;
up[node][0]=ata;
ger[node][0]=dizi[ata];
for(int i=1;i<=l;i++){
up[node][i]=up[up[node][i-1]][i-1];
ger[node][i]=max(ger[node][i-1],dizi[up[node][i]]);
}
for(auto go:v[node]){
if(go==ata)continue;
dfs(go,node);
tout[node]=max(tout[node],tout[go]);
}
}
inline bool anc(int node1,int node2){
return tin[node1]<=tin[node2] && tout[node1]>=tout[node2];
}
inline int find_lca(int node1,int node2){
if(anc(node1,node2))return node1;
if(anc(node2,node1))return node2;
for(int i=l;i>=0;i--){
if(!anc(up[node1][i],node2))node1=up[node1][i];
}
return up[node1][0];
}
inline int con(int node1,int node2){
if(node1==node2)return dizi[node1];
int cev=dizi[node1];
for(int i=l;i>=0;i--){
if(!anc(up[node1][i],node2)){
cev=max(cev,ger[node1][i]);
node1=up[node1][i];
}
}
cev=max(cev,ger[node1][0]);
return cev;
}
inline int f(int node,int mask){
//cout<<node<<endl;
if(~dp[node][mask])return dp[node][mask];
int cev=0;
FOR{
if(mask&(1<<i))continue;
int lca=find_lca(i,node);
int distance=dist[i]+dist[node]-2*dist[lca];
int maxi=0;
maxi=max(maxi,con(i,lca));
maxi=max(maxi,con(node,lca));
//cout<<node<<" "<<i<<" "<<maxi<<" "<<dizi[node]<<" "<<distance<<endl;
if(maxi<=dizi[node]){// check
cev=max(cev,f(i,mask|(1<<i))+distance);
}
}
return dp[node][mask]=cev;
}
int32_t main(){
faster
memset(dp,-1,sizeof(dp));
cin>>n;
l=ceil(log2(n));
int baslangic;
FOR{
cin>>dizi[i];
if(dizi[i]==n)baslangic=i;
}
FOR{
if(i==1)continue;
int x,y;cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
dfs(1,1);
cout<<f(baslangic,0)<<'\n';
return 0;
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa7): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xd4): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xdb): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xe2): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
collect2: error: ld returned 1 exit status
