#include<bits/stdc++.h> using namespace std; #define int long long #define lson t[now].ls #define rson t[now].rs #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=100010,N=20,inf=1e9; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT=1;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,s,q,a[MAXN],fa[MAXN],dep[MAXN],siz[MAXN],top[MAXN],son[MAXN]; void dfs(int u,int lst){ fa[u]=lst,siz[u]=1; int mx=0; for(inx(u))if(v!=lst){ dep[v]=dep[u]+1; dfs(v,u); siz[u]+=siz[v]; if(siz[v]>mx)mx=siz[v],son[u]=v; } } void dfs2(int u,int lst,int ty){ top[u]=ty; if(son[u])dfs2(son[u],u,ty); for(inx(u))if(v!=lst&&v!=son[u])dfs2(v,u,v); } struct node{ int pri,mx,x,t,lz,ls,rs; }t[MAXN];int cnt; mt19937 rng( // clock()^time(0) 1 ); struct treap{ int rt,id; void upd(int x,int y){ t[x].x-=y; t[x].mx-=y; t[x].t+=y; t[x].lz+=y; } void pushdown(int now){ if(t[now].lz){ if(lson)upd(lson,t[now].lz); if(rson)upd(rson,t[now].lz); t[now].lz=0; } } void pushup(int now){ t[now].mx=t[now].t; if(lson)t[now].mx=max(t[now].mx,t[lson].mx); if(rson)t[now].mx=max(t[now].mx,t[rson].mx); } int mrge(int x,int y){ if(!x||!y)return x|y; pushdown(x),pushdown(y); if(t[x].pri>t[y].pri){ t[x].rs=mrge(t[x].rs,y); pushup(x); return x; } else{ t[y].ls=mrge(x,t[y].ls); pushup(y); return y; } } pii split(int now,int key){ if(!now)return mk(0,0); pushdown(now); if(t[now].x<=key){ pii tmp=split(rson,key); t[now].rs=tmp.fr; pushup(now); return mk(now,tmp.sc); } else{ pii tmp=split(lson,key); t[now].ls=tmp.sc; pushup(now); return mk(tmp.fr,now); } } void dfs(int now){ if(!now)return; pushdown(now); dfs(lson); // cout<<"dfs "<<now<<","<<t[now].x<<" "<<t[now].mx<<" "<<t[now].lz<<" "<<t[now].ls<<" "<<t[now].rs<<endl; dfs(rson); } int nnd(int x,int T){ t[++cnt]={rng(),x,x,T-x,0,0,0}; // cout<<"nnd:"<<cnt<<","<<x<<" "<<T<<endl; return cnt; } void insert(int x,int t){ pii tmp=split(rt,x); rt=mrge(tmp.fr,mrge(nnd(x,t),tmp.sc)); } void insert(int x){ int dp=t[x].x; pii tmp=split(rt,dp); rt=mrge(tmp.fr,mrge(x,tmp.sc)); } int query(int d){ pii x=split(rt,d); int res=t[x.fr].mx; rt=mrge(x.fr,x.sc); return res; } int fid(int now){ pushdown(now); if(lson)return fid(lson); else return t[now].x; } int update(int d){ pii x=split(rt,d); upd(x.fr,1); rt=mrge(x.fr,x.sc); int tmp=fid(rt),res=0; if(id!=s&&tmp<dep[id]){ x=split(rt,tmp); res=x.fr; rt=x.sc; } return res; } }p[MAXN]; void insert(int t,int x){ p[top[x]].insert(dep[x],t); } void update(int x){ while(top[x]!=s){ int tmp=p[top[x]].update(dep[x]); if(!tmp)p[fa[top[x]]].insert(tmp); x=fa[top[x]]; } // cout<<"U"<<top[x]<<" "<<x<<":"<<endl; p[top[x]].dfs(p[top[x]].rt); int tmp=p[top[x]].update(dep[x]); } int query(int x){ int res=0; while(top[x]!=s){ res=max(res,p[top[x]].query(dep[x])); x=fa[top[x]]; } // cout<<"Q"<<top[x]<<" "<<x<<":"<<endl; p[top[x]].dfs(p[top[x]].rt); res=max(res,p[top[x]].query(dep[x])); return res; } void slv(){ n=read(),s=read(); for(int i=1;i<=n;i++)a[i]=read(),p[i].id=i; for(int i=1;i<n;i++){ int u=read(),v=read(); add_side(u,v); } t[0]={0,-inf,-inf,-inf,0,0,0}; dfs(s,s),dfs2(s,s,s); insert(1,s); int ans=0; for(int i=1;i<=n;i++){ int tmp=query(i); update(i); ans=max(ans,tmp+dep[i]+a[i]); // cout<<"f["<<i<<"]:"<<tmp<<" "<<dep[i]<<" "<<a[i]<<" "<<tmp+dep[i]+a[i]<<endl; insert(tmp+dep[i]+a[i]+1,i); } printf("%lld",ans); } signed main(){ //freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); //cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s\n"; return 0; }