B
很有意思的题
首先题目的要求为可以拆分成 \(2\) 个不相交的不降子序列
根据 \(dilworth\) 定理，最小链覆盖 \(=\) 最长反链，所以要求最长反链 \(\le 2\)
即原序列的逆序列的最长不降子序列长度 \(\le 2\)
不难得到一个 \(dp\) 做法为：
令 \(f_{i,j}\) 为到数 \(i\)，最长上升子序列长度为 \(j\) 的方案数
我们考虑从小到大加数（已经变成了逆序列）
可以发现，第一个数前面的一段是不会影响 \(lis\) 长度的，不妨枚举其长度，对于最前面的一个加数区间，后面的序列是要舍弃的，所以需要枚举第一个加数区间
上面的转移建议自己想，不难
时间复杂度 \(O(n^3)\)
这道题目的关键在于：转化为流问题，用 \(dilworth\)，得到求逆序列 \(lis\) 长度 \(\le 2\) 的序列个数
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=510,P=998244353;
int n,a[N],f[N][N],C[N][N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
read(n);
C[0][0]=1;
F(i,1,N-1) F(j,0,i) C[i][j]=(!j||i==j)?1:(C[i-1][j-1]+C[i-1][j])%P;
F(i,1,n) read(a[n-i+1]);
int res=0;
f[0][0]=1;
F(i,1,n){
if(!a[i]){ F(j,0,res) f[i][j]=f[i-1][j];continue;}
F(j,0,res){
F(k,1,j){
int le=j-k+1;
F(t,0,a[i]-1) inc(f[i][k+t],1ll*f[i-1][j]*C[a[i]-1-t+le-1][a[i]-1-t]%P);
}
inc(f[i][j+a[i]],f[i-1][j]);
}
res+=a[i];
}
int ans=0;
F(i,1,res) inc(ans,f[n][i]);
printf("%d\n",ans);
return 0;
}
C
\(PAM\) 板子题
没学过 \(PAM\)，现场贺了一份板子上去
一个技巧是倍长字符串，但也比较套路了
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
using namespace std;
const int N=6e6+100,P=998244353;
char str[N];
int n,s[N],res[N];
int p,q,fail[N],cnt[N],len[N],tot,last,ch[N][10];
inline int newnode(int x){
len[++tot]=x;return tot;
}
inline int getfail(int x,int n){
while(s[n-len[x]-1]!=s[n]) x=fail[x];
return x;
}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
void work(int neg){
for(int i=0;i<=n;i++){
cnt[i]=fail[i]=len[i]=0;
for(int j=0;j<=9;j++) ch[i][j]=0;
}
p=0,q=0;
s[0]=-1,fail[0]=1,last=0;
len[0]=0,len[1]=-1,tot=1;
for(int i=1;i<=n;i++){
p=getfail(last,i);
if(!ch[p][s[i]]){
q=newnode(len[p]+2);
fail[q]=ch[getfail(fail[p],i)][s[i]];
ch[p][s[i]]=q;
}
++cnt[last=ch[p][s[i]]];
}
for(int i=tot;i;--i) cnt[fail[i]]+=cnt[i];
for(int i=1;i<=tot;i++) res[i]+=cnt[i]*neg;
}
int main(){
n=read();
scanf("%s",str+1);
for(int i=1;i<=n;i++) s[i]=str[i]-'0';
work(-1);
for(int i=1;i<=n;i++) s[i+n]=s[i];
n<<=1;work(1);
int ans=0;
for(int i=1;i<=tot;i++) if(len[i]<=n/2)
ans=(ans+1ll*len[i]*res[i]%P*res[i])%P;
printf("%d\n",ans);
return 0;
}
D
枚举 \(i\) 之后题目变得很不可做
考虑换个角度，枚举 \(k\)
不难发现，合法的 \(i\) 是一个前缀
不妨二分 \(i\)，判断合法直接字符串哈希看：\(hash[1,mid-2k]+hash[2k+1,mid]=2hash[2k+1,mid-2k]\)
时间复杂度 \(O(n\log n)\)
这道题的关键在于想到枚举 \(k\) 和哈希
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=2000100;
int n,tag[N],a[N],base[6];
int gtnum(char x){
if('0'<=x&&x<='9') return x-'0';
if('a'<=x&&x<='z') return 10+x-'a';
if('A'<=x&&x<='Z') return 36+x-'A';
}
struct Hash{
int base,mod,p[N],h[N];
void build(){
p[0]=1;
F(i,1,n) p[i]=1ll*p[i-1]*base%mod;
F(i,1,n) h[i]=(1ll*h[i-1]*base+a[i])%mod;
}
int gethash(int l,int r){ return (h[r]-1ll*h[l-1]*p[r-l+1]%mod+mod)%mod;}
}hash1,hash2;
int main(){
n=read();
base[0]=1;
F(i,1,4) base[i]=base[i-1]*62;
F(i,1,n){
string s;cin>>s;
DF(j,SZ(s),0) a[i]+=base[SZ(s)-j]*gtnum(s[j]);
}
hash1.base=31,hash1.mod=1e9+7,hash2.base=131,hash2.mod=998244353;
hash1.build(),hash2.build();
F(k,1,n/2){
int l=k*2,r=n+1;
while(l<r-1){
int mid=(l+r)>>1;
if((hash1.gethash(1,mid-2*k)+hash1.gethash(2*k+1,mid))%hash1.mod==hash1.gethash(k+1,mid-k)*2%hash1.mod
&&(hash2.gethash(1,mid-2*k)+hash2.gethash(2*k+1,mid))%hash2.mod==hash2.gethash(k+1,mid-k)*2%hash2.mod) l=mid;
else r=mid;
}
tag[k*2+1]++,tag[l+1]--;
}
F(i,1,n) tag[i]+=tag[i-1],putchar((tag[i]>0)+48);
return 0;
}
E
签到题，发现 \(x\) 轴和 \(y\) 轴互不影响
直接对于 \(x\) 轴和 \(y\) 轴分别跑一遍一维距离统计即可
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=1100;
int n,m,a[N][N],disc[N*N];
LL s1[N*N],s2[N*N];
signed main(){
n=read(),m=read();
LL ans=0;
int cnt=0;
F(i,1,n) F(j,1,m) a[i][j]=read(),disc[++cnt]=a[i][j];
sort(disc+1,disc+cnt+1);
cnt=unique(disc+1,disc+cnt+1)-disc-1;
F(i,1,n) F(j,1,m) a[i][j]=lower_bound(disc+1,disc+cnt+1,a[i][j])-disc;
F(i,1,n){
F(j,1,m) ans+=s2[a[i][j]]*i-s1[a[i][j]];
F(j,1,m) s1[a[i][j]]+=i,s2[a[i][j]]++;
}
F(i,1,cnt) s1[i]=s2[i]=0;
F(j,1,m){
F(i,1,n) ans+=s2[a[i][j]]*j-s1[a[i][j]];
F(i,1,n) s1[a[i][j]]+=j,s2[a[i][j]]++;
}
printf("%lld\n",ans*2);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}
F
更签到的题，不讲了
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
int n;
map<string,int> mp;
int main(){
cin>>n;
F(i,1,n){
string s;cin>>s;
mp[s]++;
}
for(auto it:mp) if(it.second*2>n){ cout<<it.first<<'\n';exit(0);}
cout<<"uh-oh"<<'\n';
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}
G
不难的题
不难想到二分，然后的 \(nk\) \(dp\) 就比较显然，需要前缀和优化
时间复杂度 \(O(nk\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=200100,K=10;
int n,m,k,l[K],s[N],pref[N],f[N][K];
char str[N];
bool a[N];
bool check(int mid){
memset(f,0x3f,sizeof(f));
F(i,0,mid-1) f[i][0]=0;
F(i,mid,n){
int pos=pref[i-mid];
if(!pos){ f[i][0]=f[i-1][0],f[i][1]=min(f[i-1][1],i-s[i]);continue;}
F(j,1,k) f[i][j]=f[pos-1][j-1]+i-pos-(s[i]-s[pos]);
F(j,0,k) f[i][j]=min(f[i][j],f[i-1][j]);
}
return f[n][k]<=m;
}
int main(){
n=read(),m=read(),k=read();scanf("%s",str+1);
F(i,1,n) a[i]=str[i]-48,s[i]=s[i-1]+a[i];
int cur=0;
F(i,1,n){
if(!a[i]) cur=i;
pref[i]=cur;
}
if(!check(1)){ puts("-1");exit(0);}
int l=0,r=n+1;
while(l<r-1){
int mid=(l+r)>>1;
check(mid)?l=mid:r=mid;
}
printf("%d\n",l);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}
I
有点暴力的题，感觉题面吓人导致过的队有点少
一个易想到的判断是一个字母的出现次数，但这会有冲突
于是我打了个表，发现冲突很少，且每个冲突的出现次数都很小
于是可以把冲突的字母暴力匹配然后判断即可
时间复杂度 \(O(\)能过\()\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=60;
int n,rv[N],id[N];
bool vis[N];
int gt(char x){
if('a'<=x&&x<='z') return x-'a';
return 26+x-'A';
}
vector<int> inc[N*N*2];
int len,CNT[N],cnt[N];
int ID1[N],ID2[N],dy[N];
map<pii,int> mp2;
map<int,int> mp1;
string s[N*N];
int L[N],R[N];
bool dfs(int dep){
if(dep>len){
map<int,int> tmpmp1=mp1;
map<pii,int> tmpmp2=mp2;
F(i,1,len) rv[ID1[dy[i]]]=ID2[i];
bool flg=1;
F(i,0,n-1){
F(j,0,n-1){
int t=i*j;
int x=t/n,y=t%n;
if(!x){
if(rv[y]!=-1){
if(!tmpmp1[rv[y]]){ flg=0;break;}
tmpmp1[rv[y]]--;
}
}
else if(rv[x]!=-1&&rv[y]!=-1){
if(!tmpmp2[make_pair(rv[x],rv[y])]){ flg=0;break;}
tmpmp2[make_pair(rv[x],rv[y])]--;
}
}
if(!flg) break;
}
if(flg) return true;
return false;
}
F(j,L[dep],R[dep]) if(!vis[j]){
dy[dep]=j,vis[j]=1;
if(dfs(dep+1)) return true;
vis[j]=0;
}
return false;
}
void work(){
n=read();
F(i,0,n-1) CNT[i]=cnt[i]=0;
mp2.clear(),mp1.clear();
F(i,0,n*n*2) inc[i].clear();
F(i,1,n*n){
cin>>s[i];
F(j,0,SZ(s[i])) CNT[gt(s[i][j])]++;
if(s[i].size()==2) mp2[{gt(s[i][0]),gt(s[i][1])}]++;
else mp1[gt(s[i][0])]++;
}
F(i,0,n-1) inc[CNT[i]].pb(i);
F(i,0,n-1) F(j,0,n-1){
int t=i*j;
if(!(t/n)) cnt[t%n]++;
else cnt[t/n]++,cnt[t%n]++;
}
F(i,0,n-1) id[i]=i;
F(i,0,n-1) rv[i]=-1;
sort(id,id+n,[&](int x,int y){ return cnt[x]<cnt[y];});
for(int i=0;i<n;){
int j=i;
while(j<n-1&&cnt[id[j+1]]==cnt[id[i]]) j++;
if(!(j-i)) rv[id[i]]=inc[cnt[id[i]]][0];
i=j+1;
}
len=0;
for(int i=0;i<n;){
int j=i;
while(j<n-1&&cnt[id[j+1]]==cnt[id[i]]) j++;
if(j-i>0){
int tlen=len;
F(k,i,j) ID1[++tlen]=id[k],L[tlen]=len+1,R[tlen]=len+j-i+1;
for(auto x:inc[cnt[id[i]]]) ID2[++len]=x;
}
i=j+1;
}
if(len){
F(k,1,len) vis[k]=0;
dfs(1);
}
F(i,0,n-1){
if(rv[i]<26) putchar('a'+rv[i]);
else putchar('A'+rv[i]-26);
}
puts("");
}
int main(){
int T=read();
while(T--) work();
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}
J
\(sb\) 题，直接魔改最短路，然后枚举最长边即可
时间复杂度 \(O(m\log m)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=300100,M=1000100,inf=2e9;
int n,m;
int e[M<<1],w[M<<1],ne[M<<1],h[N],idx;
void add(int x,int y,int z){ e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}
bool vis[N];
priority_queue<pii,vector<pii>,greater<pii> > pq;
void dij(int S,int *d){
F(i,1,n) d[i]=inf,vis[i]=0;
d[S]=0,pq.push({0,S});
while(!pq.empty()){
int u=pq.top().second;pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(max(d[u],w[i])<d[v]) d[v]=max(d[u],w[i]),pq.push({d[v],v});
}
}
}
int d[2][N];
int main(){
n=read(),m=read();
ms(h,-1);
F(i,1,m){
int x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
dij(1,d[0]),dij(n,d[1]);
int ans=inf+100;
F(i,0,idx-1){
int x=e[i],y=e[i^1];
if(d[0][x]<=w[i]&&d[1][y]<=w[i]) chkmin(ans,w[i]+max(d[0][x],d[1][y]));
}
for(int i=h[1];~i;i=ne[i]) if(e[i]==n) chkmin(ans,w[i]);
printf("%d\n",ans);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}
K
首先可以发现一个性质是一个连通块只可能是一段路径，因为路径两端是最大值和次大值一定是最优的，其他的分开这个连通块更优
然后可以设计出一个朴素的 \(dp\) 做法是：
令 \(f_{i,j}\) 为 \(i\) 的子树中一端权值为 \(j\) 的最大权值和
\(g_i\) 为 \(i\) 的子树能形成的最大权值和
合并子树 \(v\) 时：
\(f_{i,j}=\max\{f_{i,j}+g_v,f_{v,j}+otherg\}\)
\(g_i=\max\{f_{u,j}+f_{v,k}+min(j,k)\}\)
发现上面的东西可以套线段树合并，直接套即可
时间复杂度 \(O(n\log n)\)
这道题感觉 \(dp\) 的设计比较巧妙
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=500100;
const LL inf=1e16;
int n;LL g[N],G;
int cnt,disc[N],w[N];
int e[N<<1],ne[N<<1],h[N],IDX;
int root[N],idx;
struct Node{ LL mx1,mx2,tag;int lc,rc;}seg[N*30];
void down(int x,LL tg){ if(x) seg[x].mx1+=tg,seg[x].mx2+=tg,seg[x].tag+=tg;}
void pushdown(int x){ down(seg[x].lc,seg[x].tag),down(seg[x].rc,seg[x].tag),seg[x].tag=0;}
void calc(int p,int q,int l,int r,LL mx1,LL mx2){
if(!p&&!q) return;
if(!p){ chkmax(G,mx1+seg[q].mx2);return;}
if(!q){ chkmax(G,mx2+seg[p].mx2);return;}
if(l==r){
chkmax(mx1,seg[p].mx1),chkmax(mx2,seg[q].mx1);
chkmax(G,max(seg[p].mx2+mx2,seg[q].mx2+mx1));return;
}
pushdown(p),pushdown(q);
int mid=(l+r)>>1;
calc(seg[p].lc,seg[q].lc,l,mid,max(mx1,seg[seg[p].rc].mx1),max(mx2,seg[seg[q].rc].mx1));
calc(seg[p].rc,seg[q].rc,mid+1,r,mx1,mx2);
}
int insert(int l,int r,int pos){
int p=++idx;seg[p].mx1=0,seg[p].mx2=disc[pos];
if(l==r) return p;
int mid=(l+r)>>1;
if(mid>=pos) seg[p].lc=insert(l,mid,pos);
else seg[p].rc=insert(mid+1,r,pos);
return p;
}
int merge(int p,int q,int l,int r,LL coef1,LL coef2){
if(!p&&!q) return 0;
if(!p){ seg[q].mx1+=coef2,seg[q].mx2+=coef2,seg[q].tag+=coef2;return q;}
if(!q){ seg[p].mx1+=coef1,seg[p].mx2+=coef1,seg[p].tag+=coef1;return p;}
if(l==r){ seg[p].mx1=max(seg[p].mx1+coef1,seg[q].mx1+coef2),seg[p].mx2=max(seg[p].mx2+coef1,seg[q].mx2+coef2);return p;}
pushdown(p),pushdown(q);
int mid=(l+r)>>1;
seg[p].lc=merge(seg[p].lc,seg[q].lc,l,mid,coef1,coef2);
seg[p].rc=merge(seg[p].rc,seg[q].rc,mid+1,r,coef1,coef2);
seg[p].mx1=max(seg[seg[p].lc].mx1,seg[seg[p].rc].mx1);
seg[p].mx2=max(seg[seg[p].lc].mx2,seg[seg[p].rc].mx2);return p;
}
void dfs(int u,int fa){
LL sumg=0;root[u]=insert(1,n,w[u]);
for(int i=h[u];~i;i=ne[i]){
int v=e[i];if(v==fa) continue;
dfs(v,u);
g[u]+=g[v],G=0;calc(root[u],root[v],1,n,-inf,-inf);chkmax(g[u],G);
root[u]=merge(root[u],root[v],1,n,g[v],sumg);
sumg+=g[v];
}
}
void add(int x,int y){ e[IDX]=y,ne[IDX]=h[x],h[x]=IDX++;}
int main(){
seg[0].mx1=-inf,seg[0].mx2=-inf;
n=read();
F(i,1,n) w[i]=read(),disc[++cnt]=w[i];
sort(disc+1,disc+n+1);
int cnt=unique(disc+1,disc+n+1)-disc-1;
F(i,1,n) w[i]=lower_bound(disc+1,disc+cnt+1,w[i])-disc;
ms(h,-1);
F(i,1,n-1){
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs(1,-1);
printf("%lld\n",g[1]);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}